[SDOI2012] Longge 的问题

题意

求(sum_{i}^{n} gcd(i,n))

想法

套路题
(sum_{i}^{n} gcd(i,n)) (=) (sum_{i,i | n} i * phi（n/i）)
枚举(i)暴力求(phi)

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long

ll n;

ll phi(ll now){
	ll ans = now;
	for(ll i = 2;i * i <= now;++i){
		if(now % i == 0){
			ans = ans / i * (i - 1);
			while(now % i == 0) now /= i;
		}
	}
	if(now > 1) ans = ans / now * (now - 1);
	return ans;
}

ll ans = 0;

int main(){
	scanf("%lld",&n);
	ll s = sqrt(n);
	for(ll i = 1;i <= s;++i){
		if(n % i == 0){
			ans += phi(n / i) * i;
			if(i * i != n)
			ans += phi(i) * (n / i);
		}
	}
	std::cout<<ans<<std::endl;
}