洛谷P2303 [SDOI2012] Longge的问题

数论蒟蒻来写题解啦因为太弱所以只敢写在这里。

题面：
Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。$n\le 2^{32}$

思路：暴力枚举是不可能的，但是发现$n$是一直存在的，那么答案只有可能是$n$的约数，所以考虑枚举答案统计贡献。

那么我们把问题变成了

$$ans=\sum _{d|n}d\times \sum _{i=1}^n[gcd(i,n)=d]$$
一起除个$d$
$$ans=\sum _{d|n}d\times \sum _{i=1}^n[gcd(\frac{i}{d},\frac{n}{d})=1]$$
把$i$的那个除号提出来
$$ans=\sum _{d|n}d\times \sum _{i=1}^{\frac{n}{d}}[gcd(i,\frac{n}{d})=1]$$
应该很好理解吧。

然后我们发现：这不就是欧拉函数吗？？？
$$ans=\sum _{d|n}d\times ?(\frac{n}{d})$$

然后复杂度不会用$O$写，大概就是$(\sum _{d|n}\sqrt{d})$+$\sqrt{n}$

实际上跑得飞快。

如果你还想优化，可以预处理$\sqrt{n}$以内的质数，优化$\sqrt{d}$的那部分复杂度。

$code$

#include<bits/stdc++.h>
using namespace std;
#define int long long
int euler(int a){
    int ans=a;for(int i=2;i*i<=a;++i)if(a%i==0){
    ans=ans/i*(i-1);while(a%i==0)a/=i;}if(a!=1)ans=ans/a*(a-1);return ans;
}
int n,ans;
signed main(){
    scanf("%lld",&n);for(int i=1;i*i<=n;++i)if(n%i==0){
    ans+=i*euler(n/i);if(i!=n/i) ans+=(n/i)*euler(i);}printf("%lld",ans);return 0;
}