andyli

题解 UVA11426 【拿行李(极限版) GCD - Extreme (II)】
设$f(n)=\gcd(1,n)+\gcd(2,n)+\gcd(3,n)+...+\gcd(n-1,n)$,则所求...
扫描右侧二维码阅读全文
20
2019/06

题解 UVA11426 【拿行李(极限版) GCD - Extreme (II)】

设$f(n)=\gcd(1,n)+\gcd(2,n)+\gcd(3,n)+...+\gcd(n-1,n)$,则所求答案为$S(n)=f(2)+f(3)+...+f(n)$。只需求出$f(n)$,就可以递推出所有答案:$S(n)=S(n-1)+f(n)$。因此,本题的重点在于如何计算$f(n)$。
注意到所有$\gcd(x,n)$的值都是$n$的约数,可以按照这个约数进行分类,用$g(n,i)$表示满足$gcd(x,n)=i$且$x<n$的正整数$x$的个数,则$f(n)=sum\{i\times g(n,i)|i\text{是}n\text{的约数}\}$。注意到$\gcd(x,n)=i$的充要条件是$\gcd(x/i,n/i)=1$,因此满足条件的$x/i$有$phi(n/i)$个,说明$g(n,i)=phi(n/i)$。
问题到这里还没有结束。如果依次计算$f(n)$,需要对每个$n$枚举它的约数$i$,速度较慢,但如果把思路逆转过来,对于每个$i$枚举它的倍数$n$(并且更新$f(n)$的值),时间复杂度将降为与素数筛法同阶。至此,问题得到了完整的解决。代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4000000;
typedef long long LL;

int phi[maxn];
void phi_table(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
        if (!phi[i])
            for (int j = i; j <= n; j += i)
            {
                if (!phi[j])
                    phi[j] = j;
                phi[j] = phi[j] / i * (i - 1);
            }
}
LL S[maxn + 1], f[maxn + 1];
int main()
{
    phi_table(maxn);
    for (int i = 1; i <= maxn; i++)
        for (int n = i * 2; n <= maxn; n += i)
            f[n] += i * phi[n / i];
    S[2] = f[2];
    for (int n = 3; n <= maxn; n++)
        S[n] = S[n - 1] + f[n];
    int n;
    while (~scanf("%d", &n) && n)
        printf("%lld\n", S[n]);
    return 0;
}
Last modification:June 25th, 2019 at 11:21 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment