51Nod 1237 最大公约数之和 V3

给出一个数N，输出小于等于N的所有数，两两之间的最大公约数之和。

相当于计算这段程序（程序中的gcd(i,j)表示i与j的最大公约数）：
由于结果很大，输出Mod 1000000007的结果。
```
G=0;
for(i=1;i<N;i++)
for(j=1;j<=N;j++)
{
    G = (G + gcd(i,j)) % 1000000007;
}
```
Input
输入一个数N。(2 <= N <= 10^10)
Output
输出G Mod 1000000007的结果。
Input示例
100
Output示例
31080

推导：
$$\sum^n_{i = 1}\sum^n_{j = 1}gcd(i, j)$$
$$\sum^n_{d=1}d\cdot \sum^n_{i = 1}\sum^n_{j = 1}[gcd(i, j)=d]$$
$$\sum^n_{d=1}d\cdot \sum^{\frac{n}{d}}_{i = 1}\sum^{\frac{n}{d}}_{j = 1}[gcd(i, j)=1]$$
....
....
详见最小公倍数之和V3
....
....
推导到最后：
$$\sum^n_{i=1}i\cdot \sum^{\frac{n}{i}}_{j=1}\phi(j)$$
求$\phi$函数的前缀和，变成了杜教筛的形式，可以过了。

```
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<tr1/unordered_map>
#define LL long long
#define sqr(x) ((x) * (x))
using namespace std;
using namespace tr1;
const int maxn = 6e6 + 6;
const LL mod = 1e9 + 7;
int pri[maxn], vis[maxn];
LL n, m, ans, phi[maxn], inv4, inv2, inv6, s[maxn];
unordered_map<LL, LL> hsh;
LL s1(LL x) {return x %= mod, ((x + 1) * x % mod) * inv2 % mod;}
LL fpow(LL a, LL b, LL c) {
    LL ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % c;
        a = a * a % c, b >>= 1;
    }
    return ans;
}
void GetPri(int N) {
    vis[1] = phi[1] = s[1] = 1;
    for(register int i = 1; i <= N; ++i) {
        if(!vis[i]) pri[++pri[0]] = i, phi[i] = i - 1;
        for(register int j = 1; j <= pri[0] && i * pri[j] <= N; ++j) {
            vis[i * pri[j]] = 1;
            phi[i * pri[j]] = phi[i] * phi[pri[j]];
            if(i % pri[j] == 0) {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
        }
    }
    for(register int i = 1; i <= N; ++i) {
        (s[i] = s[i - 1] + phi[i]) %= mod;
    }
}
LL GetSum(LL x) {
    if(x <= m) return s[x];
    if(hsh[x]) return hsh[x];
    LL ret = s1(x);
    LL l = 2, r = 1, a;
    while(r < x) {
        l = r + 1, r = x / (x / l);
        a = GetSum(x / l), ret = (ret - (r - l + 1) * a % mod) % mod;
        hsh[x / l] = a;
    }
    return (ret + mod) % mod;
}
int main() {
    scanf("%lld", &n);
    m = (int)pow(n, 2.0 / 3.0) + 100;
    inv2 = fpow(2, mod - 2, mod);
    GetPri(m);
    LL l = 1, r = 0;
    while(r < n) {
        l = r + 1, r = n / (n / l);
        (ans += (GetSum(n / r) % mod) * ((s1(r) - s1(l - 1)) % mod)) %= mod;
    }
    printf("%lld", ((2 * ans - s1(n)) % mod + mod) % mod);
    return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链