UVA11417 GCD


题目地址

题目链接

题解

先讨论任何没有限制的情况
\[ \large { \begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)\\ &=\sum_{k=1}^{n}k\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)=k]\\ &=\sum_{k=1}^{n}k\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum_{j=1}^{\lfloor \frac{n}{k}\rfloor }[gcd(i,j)=1]\\ &=\sum_{k=1}^{n}k\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum_{j=1}^{\lfloor \frac{n}{k}\rfloor }\sum_{d|gcd(i,j)}\mu(d)\\ &=\sum_{k=1}^{n}k\sum_{d=1}^{n}{\mu(d)\lfloor \frac{n}{kd}\rfloor^2} \end{aligned} } \]

因为这个公式里面,我们对于所有的(i,j),同时也算了(j,i)

显然gcd(i,j)=gcd(j,i)

所以只需要除以2即可

但是因为对于所有的(i,i)。我们只算了一次,因为这个在答案中不算进去,所以我们可以直接减掉再除以2

所以最后的答案
\[ \large ANS= \frac{\sum_{k=1}^{n}k\sum_{d=1}^{n}{\mu(d)\lfloor \frac{n}{kd}\rfloor^2}-\sum_{i=1}^{n}i}{2} \]
用容斥的思想来理解就很简单了

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 501
int n;
int vis[N], p[N], cnt = 0, mu[N], sum[N];

void init() {
    mu[1] = sum[1] = 1;
    for(int i = 2; i < N; ++i) {
        if(!vis[i]) {p[++cnt] = i; mu[i] = -1;}
        for(int j = 1; j <= cnt && p[j] * i < N; ++j) {
            vis[p[j] * i] = 1;
            if(i % p[j] == 0) break;
            mu[i * p[j]] -= mu[i];
        }
        sum[i] = sum[i - 1] + mu[i];
    }
}

int calc(int m, int k) {
    int ans = 0;
    for(int l = 1, r; l <= m; l = r + 1) {
        r = m / (m / l);
        ans += (n / l / k) * (n / l / k) * (sum[r] - sum[l - 1]);
    }
    return ans;
}

int main() {
    init();
    while(scanf("%d", &n) == 1 && n) {
        int ans = 0;
        for(int i = 1; i <= n; ++i) {
            ans += i * calc(n, i);
        }
        printf("%d\n", (ans - (n * (n + 1)) / 2) / 2);
    }
    return 0;
}
优质内容筛选与推荐>>
1、第一次做Java程序注意事项
2、[转载]NSString+NSMutableString+NSValue+NSAraay用法汇总
3、Fragments (官方文档中文版)
4、51nod 1120 机器人走方格 V3
5、汇编-PC硬件基本特征


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号