hdu 6889
傳說(shuō)中的人均min25

題意：

n個(gè)點(diǎn)的完全圖，邊權(quán)為lcm(i+1,j+1)，求mst（最小生成樹(shù)）

題解：

我一開(kāi)始以為是推公式，畢竟數(shù)據(jù)范圍這么大，但是自己畫(huà)圖來(lái)看看mst的情況
注意求lcm時(shí)每個(gè)點(diǎn)都要加一，所以后面說(shuō)點(diǎn)數(shù)時(shí)默認(rèn)加一
首先，節(jié)點(diǎn)2要與所有質(zhì)數(shù)相連，因?yàn)橘|(zhì)數(shù)與任何數(shù)x（x>1）的lcm都是質(zhì)數(shù)乘x，x最小就是2，所以所有指數(shù)要與2相連，那非質(zhì)數(shù)呢？非質(zhì)數(shù)就肯定有除1和本身外的因數(shù)，那就與因數(shù)相連，lcm也就是其本身（其實(shí)如果為偶數(shù)，也可以與2相連，畢竟2是所有偶數(shù)的因子）
最終的結(jié)果就是：
(n+1范圍內(nèi))
（∑(質(zhì)數(shù)）-2) * 2+∑非質(zhì)數(shù)
∑非質(zhì)數(shù) = 總數(shù)和-∑質(zhì)數(shù)
總數(shù)和 = 2+3+4+…n+1 = (2+n+1)n/2=(n+3)n/2
∑(質(zhì)數(shù)） 2 - 4+總數(shù)和-∑質(zhì)數(shù)
∑質(zhì)數(shù)+總數(shù)和-4 = [3,n+1]的素?cái)?shù)和+(3+4…+(n+1))= [3,n+1]的素?cái)?shù)和+ (n+4) * (n-1)/2

減2是因?yàn)楣?jié)點(diǎn)2不能與自身相連
注意n的范圍是10¹⁰，這玩意咋寫？？
有個(gè)神奇的算法叫min25篩（詳細(xì)看知乎），本題代碼模板也選自知乎
比賽時(shí)也出現(xiàn)大量知乎借鑒現(xiàn)象，可唯獨(dú)我就是沒(méi)做出來(lái)，難受
通過(guò)min25篩就可以在規(guī)定時(shí)間內(nèi)算出∑（質(zhì)數(shù)），這樣問(wèn)題就解決了

代碼：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N = 1000010;typedef long long ll;ll mod; ll qpow(ll a, ll b) {ll ans = 1;while(b){if(b & 1)ans = ans * a % mod;a = a * a % mod;b /= 2;}return ans % mod; }ll prime[N], id1[N], id2[N], flag[N], ncnt, m;ll g[N], sum[N], a[N], T, n;inline ll ID(ll x) {return x <= T ? id1[x] : id2[n / x]; }inline ll calc(ll x) {return x * (x + 1) / 2 - 1; }inline ll f(ll x) {return x; }inline void init() {ncnt = m = 0;T = sqrt(n + 0.5);for (ll i = 2; i <= T; i++){if (!flag[i])prime[++ncnt] = i, sum[ncnt] = sum[ncnt - 1] + i;for (ll j = 1; j <= ncnt && i * prime[j] <= T; j++){flag[i * prime[j]] = 1;if (i % prime[j] == 0)break;}}for (ll l = 1; l <= n; l = n / (n / l) + 1){a[++m] = n / l;if (a[m] <= T)id1[a[m]] = m;elseid2[n / a[m]] = m;g[m] = calc(a[m]);}for (ll i = 1; i <= ncnt; i++)for (ll j = 1; j <= m && (ll)prime[i] * prime[i] <= a[j]; j++)g[j] = g[j] - (ll)prime[i] * (g[ID(a[j] / prime[i])] - sum[i - 1]); }inline ll solve(ll x) {if (x <= 1)return x;return n = x, init(), g[ID(n)]; }int main() {ll n, t;scanf("%lld", &t);while(t--) {scanf("%lld%lld", &n, &mod);ll ans = (solve(n + 1) - 2 + mod) % mod;//質(zhì)數(shù)和 ll inv2 = qpow(2, mod - 2) % mod;ll tmp = ((n + 4) % mod * (n-1) % mod) % mod * inv2 % mod;printf("%lld\n", (ans + tmp) % mod);} }

總結(jié)

以上是生活随笔為你收集整理的HDU 6889 Graph Theory Class(CCPC网络赛)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。