BZoj2705: [SDOI2012]Longge的问题

2705: [SDOI2012]Longge的问题

Time Limit: 3 Sec   Memory Limit: 128 MB Submit: 2537   Solved: 1552 [ Submit][ Status][ Discuss]

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。

gcd(i,n)=d*gcd(i/d,n/d)=d*1;(d为i和n的最大公约数）

可以枚举d(1-sqrt(n)),对于每一个d对应的i的个数为n/d的欧拉函数，同时也要计算n/d对应的i的个数，为d的欧拉函数，注意当d*d==n时只能加一次

#include<stdio.h> #define LL long long LL euler(LL n) { LL ans=n; for(LL i=2;i*i<=n;i++) { if(n%i==0) ans=ans*(i-1)/i; while(n%i==0) n/=i; } if(n>1) ans=ans*(n-1)/n; return ans;  }   int main()  {   LL n,i,sum;   scanf("%lld",&n);   sum=0;   for(i=1;i*i<=n;i++)   {   if(n%i!=0)   continue;   sum+=i*euler(n/i); if(i*i!=n) sum+=n/i*euler(i);  } printf("%lld\n",sum); return 0;  }