jzoj 1349_最大公约数_数论

发布于 2017-07-14  11 次阅读


题目描述

小菜的妹妹小诗就要读小学了!正所谓计算机要从娃娃抓起,小菜决定在幼儿园最后一段轻松的时间里教妹妹编程。
小菜刚教完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]);
    }
}

 

]]>


「墨泼三千烟火,许你一世迷离」