51nod 1237 最大公约数之和 V3

求∑_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的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。