jzoj 1349_最大公约数_数论

lzusa 发布于 2020-08-20 0 次阅读

题目描述 小菜的妹妹小诗就要读小学了！正所谓计算机要从娃娃抓起，小菜决定在幼儿园最后一段轻松的时间里教妹妹编程。
小菜刚教完gcd即最大公约数以后，一知半解的妹妹写了如下一段代码：
 sum:=0;
 for i:=1 to n-1 do
 for j:=i+1 to n do sum:=sum+gcd(i,j) 显然这个程序的效率是很低的，小明打算写一个更强的程序，在求出sum的同时比妹妹跑的更快。  

思路

题目叫我们求出 $$\sum_{i=1}^{n-1} \sum_{j=i+1}^n gcd(i,j)$$
 很显然直接求是会爆炸的，所以考虑以下情况: 如果要求 $$\sum_{i=1}^{n} gcd(i, n)$$ 的时候  设$gcd(i,n) = k$  我们要计算有多少个i满足$gcd(i,n) = k$的条件 ，设满足条件的有m个数 答案就要加上 m*k; 那么如何求m呢 显然当i, n 同时除掉他们的gcd时他们的gcd会为1； 即变为$gcd(i/k,n/k) = 1$  此时i/k 和 n/k 互质， 那么就有$\phi(n/k)$个数和i/k 互质，即$m = \phi(n/k)$  那么$$\sum_{i=1}^{n} gcd(i, n) = \sum  k*\phi(n/k)$$  本题类似: 设 $sum(i) = sum(i - 1) + gcd(1,n) + gcd(2,n)+...+gcd(i-1,n)$ $f(i) = gcd(1,n) + gcd(2,n) + ... + gcd(n - 1,n) = \sum  k * \phi(n/k) $ k是n的因子 对于phi我们可以用线筛筛出来，然后在预处理f 和 sum 后直接输出即可
 
#include 
#define maxn 1000001
bool notPrime[maxn];
long long prime[maxn], phi[maxn], f[maxn], sum[maxn];
int work(int n)
{
    phi[1] = 1;
    int t = 0;
    for (int i = 2; i <= n; i++)
    {
        if (!notPrime[i])
        {
            prime[++t] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= t && prime[j] * i < n; j++)
        {
            notPrime[i * prime[j]] = 1; 
            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
}
int main()
{
    int t;
    work(maxn - 1);
    for (int i = 1; i < maxn; i++)
        for (int j = i * 2; j < maxn; j += i)
            f[j] += i * phi[j / i];
    for (int i = 2; i < maxn; i++) sum[i] += sum[i - 1] + f[i];
    scanf("%d", &t);
    for (int i = 1; i <= t; i++)
    {
        int x;
        scanf("%d", &x);
        printf("%lld\n", sum[x]);
    }
}

 

]]>