gcd-洛谷P2398 GCD SUM

https://www.luogu.org/problem/show?pid=2398 很有意思的题目； 这种题特别好； 代码不长，思路不浅； 题解细细看能看懂； AC之后有所收获；

---

我们设f[i]表示gcd为i的对数； 那么对答案的贡献就是f[i]*i; 怎么求f[i]呢； 我们看 包含i的因子的数是不是有（n/i）个； 那显然包含i因子的两个数 的gcd一定包含i； 换句话说，那个gcd一定是i的倍数； 所以 f[i]=(n/i)*(n/i)-f[i*2]-f[i*3]-f[i*4]….

#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<cmath> #include<cstring> #define Ll long long using namespace std; Ll n; Ll f[100001],ans; int main() { scanf("%lld",&n); for(int i=n;i;i--){ f[i]=(n/i)*(n/i); for(int j=2;i*j<=n;j++)f[i]-=f[j*i]; ans+=f[i]*i; } printf("%lld",ans); }