求∑_1<=i<=n∑_1<=j<=ngcd(i,j) % P

P = 10^9 + 7

2 <= n <= 10^10

這道題，明顯就是杜教篩

推一下公式：

利用∑_d|nphi(d) = n

ans = ∑_1<=i<=n∑_1<=j<=n∑_d|(i,j)phi(d)

? ? ? = ∑_1<=d<=n∑_1<=i<=n∑_1<=j<=n[d|(i,j)]phi(d)

? ? ? = ∑_1<=d<=nphi(d)∑_1<=i<=n∑_1<=j<=n[d|(i,j)]

? ? ? = ∑_1<=d<=nphi(d)(n / d) * (n / d)

? ? ? = ∑_1<=i<=nphi(i) * (n / i) * (n / i)

?

這樣我們就可以把i按照(n / i)分成sqrt(n)段，假如此時x = n / i，r = n / x

則[i,r]這段的(n / i)都為x，則此時的貢獻為x * x * ∑_i<=j<=rphi(j)

這樣的我們對于每一段，我們需要算[i,r]這一段的phi函數之和

令g(n) = ∑_1<=i<=nphi(i)

則我們需要算的是g(r) - g(i - 1)

那怎么算g(r)呢？因為這個時候r可能非常大

我們知道:

g(n) = n * (n + 1) / 2 - ∑_2<=i<=ng(n / i)

所以我們可以在O(n^(2/3))內等到g(n)

本來我以為這樣需要算sqrt(n)段，每一段最壞是O(n^(2/3))，所以時間復雜度是不行的，

但是試寫一下代碼，交后，發現跑的很快，大概是有很多段的g都可以很快的求出來？？？

我這里也不會算復雜度。。。

?

代碼：

?

//File Name: nod1237.cpp//Created Time: 2017年01月04日 星期三 00時47分02秒 #include <bits/stdc++.h> #define LL long long using namespace std; const int MAXN = (int)2e7 + 1; const int P = (int)1e9 + 7; bool check[MAXN]; int prime[MAXN / 10]; LL g[MAXN],inv_2; map<LL,LL> rem; void init(int n){int tot = 0;g[1] = 1;memset(check,false,sizeof(check));for(int i=2;i<=n;++i){if(!check[i]){prime[tot++] = i;g[i] = i - 1;}for(int j=0;j<tot;++j){if((LL)i * prime[j] > n) break;check[i * prime[j]] = true;if(i % prime[j] == 0){g[i * prime[j]] = g[i] * prime[j] % P;break;}else{g[i * prime[j]] = g[i] * (prime[j] - 1) % P;}}}for(int i=1;i<=n;++i)g[i] = (g[i] + g[i - 1]) % P; } LL cal_g(LL n){if(n < MAXN) return g[n];if(rem.count(n)) return rem[n];LL res = (n % P) * ((n + 1) % P) % P * inv_2 % P;for(LL i=2,x,r;i<=n;){x = n / i;r = n / x;res = (res - (r - i + 1) % P * cal_g(x) % P + P) % P;i = r + 1;}rem[n] = res;return res; } LL solve(LL n){init(min(n,MAXN - 1LL));LL res = 0;for(LL i=1,x,r;i<=n;){x = n / i;r = n / x;res = (res + (x % P) * (x % P) % P * (cal_g(r) - cal_g(i - 1) + P) % P) % P;i = r + 1;}return res; } LL qp(LL x,LL y){LL res = 1;for(;y>0;y>>=1){if(y & 1) res = res * x % P;x = x * x % P;}return res; } int main(){inv_2 = qp(2,P - 2);LL n;scanf("%lld",&n);printf("%lld\n",solve(n));return 0; }

?

轉載于:https://www.cnblogs.com/-maybe/p/6250737.html

總結

以上是生活随笔為你收集整理的51nod 1237 最大公约数之和 V3的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。