BZOJ 2705: [SDOI2012]Longge的问题

Description

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

Input

一个整数，为N。

Output

一个整数，为所求的答案。

Sample Input

6

Sample Output

15

HINT

 

【数据范围】对于60%的数据，0<N<=2^16。对于100%的数据，0<N<=2^32。

遇到数论题又跪了....

应该是属于简单题

由于N<=2^32 所以可以用用sqrt(n)的时间枚举它的约数

设gcd(n,m)=k  那么 gcd(n/k,m)=1

phi(n/k)就是满足gcd(n/k,m)=1中m的个数

所以对于确定的约束K，它对答案的贡献为 phi(n/k)*k

#include<cstdio> #include<iostream> #include<cmath> using namespace std; typedef long long ll; int phi(ll x) { ll i=2; ll ans=x; while (i*i<=x) {if (x%i==0) {ans=ans*(i-1)/i; while (x%i==0) x=x/i;} i++;} if (x>1) ans=ans*(x-1)/x; return ans; } int main() { ll n; scanf("%lld",&n); ll i=1; ll ans=0; while (i*i<=n) {if (n%i==0) { int a=i; int b=n/i; if (a!=b) ans=ans+a*phi(b)+b*phi(a); else ans=ans+a*phi(b); } i++; } printf("%lld\n",ans); }

转载于:https://www.cnblogs.com/williamchenwl/p/3634483.html

相关资源：JAVA上百实例源码以及开源项目