【bzoj2705】[SDOI2012]Longge的问题

2705: [SDOI2012]Longge的问题

Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 2507 Solved: 1531
[Submit][Status][Discuss]

Description

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

Input

一个整数，为N。

Output

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

Sample Input

Sample Output

【题解】

设gcd(m,n)=k的m的个数为s(k)，k为n的约数

则ans=sigma(k*s(k))

由gcd(m，n)=k，gcd(m/k,n/k)=1,所以s(k)=phi(n/k)

时间复杂度O(nlogn)

 /*************

   bzoj 2705

   by chty

   2016.11.4

 *************/

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<ctime>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 ll n,m,ans;

 inline ll read()

 {

     ll x=,f=;  char ch=getchar();

     while(!isdigit(ch))  {if(ch=='-')  f=-;  ch=getchar();}

     while(isdigit(ch))  {x=x*+ch-'';  ch=getchar();}

     return x*f;

 }

 ll phi(ll x)

 {

     ll sum=x;

     for(ll i=;i<=m;i++)

     {

         if(x%i==)  sum=sum/i*(i-);

         while(x%i==)  x/=i;

     }

     if(x>)  sum=sum/x*(x-);

     return sum;

 }

 int main()

 {

     freopen("cin.in","r",stdin);

     freopen("cout.out","w",stdout);

     n=read();

     m=(ll)sqrt(n*1.0);

     for(ll i=;i<=m;i++)

         if(n%i==)

         {

             ans+=i*phi(n/i);

             if(i*i<n)  ans+=(n/i)*phi(i);

         }

     printf("%lld\n",ans);

     return ;

 }

巴特西