#欧拉函数#洛谷 2303 [SDOI2012] Longge 的问题

题目

求(sum_{i=1}^ngcd(n,i))

---

分析

(=sum_{i=1}^nsum_{d|gcd(n,i)}varphi(d))
(=sum_{d|n}varphi(d)sum_{i=1}^{frac{n}{d}}1=sum_{d|n}varphi(d)frac{n}{d})
这显然可以(O(sqrt{n}log n))实现

---

代码

#include <cstdio>
#include <cctype>
#include <map>
#define rr register
using namespace std;
typedef long long lll; map<lll,bool>uk;
lll n,nn,ans,Cnt,prime[31];
inline void dfs(lll rest,lll now,lll phi){
	if (uk[now]) return;
	ans+=phi*rest,uk[now]=1;
	if (now==n) return;
	for (rr int i=1;i<=Cnt;++i)
	if (rest%prime[i]==0){
		if (now%prime[i]==0) dfs(rest/prime[i],now*prime[i],phi*prime[i]);
		    else dfs(rest/prime[i],now*prime[i],phi*(prime[i]-1));
	}
}
signed main(){
	scanf("%lld",&n),nn=n;
	for (rr lll i=2;i*i<=nn;++i)
	if (nn%i==0){
		while (nn%i==0) nn/=i;
		prime[++Cnt]=i; 
	}
	if (nn>1) prime[++Cnt]=nn;
	dfs(n,1,1);
	return !printf("%lld",ans);
}