Hdu2558(欧拉函数)

/*

欧拉函数ψ(N)=N{∏p|N}(1-1/p)亦即:ψ(N)=(P是数N的质因数)如:

ψ(10)=10×(1-1/2)×(1-1/5)=4

ψ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8

ψ(49)=49×(1-1/7)==42

*/

 

#include<iostream>

#include<cmath>

using namespace std;

 

int euler(int n){             //欧拉函数

       int ans = n;

       int s = sqrt((double)n);

       for(int i=2;i<=s; i++){

              if(n % i == 0){

                     ans = ans / i * (i - 1);

                  while(n % i == 0)

                            n /= i;

              }

       }

       if(n > 1)

              ans = ans / n * (n - 1);

       return ans;

}

 

/*

设a为大于等于m的n的一个约数,那么euler(n/a)表示的

就是所有小于a与a互质的数的个数,设任一个数为x,那

么这些数再乘以a就有gcd(n,x*a) = a;所以答案为所有n

的约数ai大于等于m的值的euler(n/ai)之和

*/

 

int main(){

       int t;

       cin>>t;

       while(t--){

              int n, m;

              cin>>n>>m;

              if(m == 1){

                     cout<<n<<endl;

                     continue;

              }

              int ans = 0;

              int s = sqrt((double)n);

              for(int i=1; i<=s; i++){

                     if(n % i == 0){

                            if(i >= m)

                                   ans += euler(n / i);

                            if(n / i >= m)

                                   ans += euler(i);

                     }

              }

              if(n > 1 && s * s == n && s >= m)

                     ans -= euler(s);

              cout<<ans<<endl;

       }

       return 0;

}

Hdu2558(欧拉函数)

上一篇:uva 11396(二分图判定)


下一篇:Cash Machine(多重背包)