hdu 2588 欧拉函数

两个数的gcd为d，其实就是将这两个数同除以d后互质。本题中n是固定的，x是小于等于n的数，很容易想到可以枚举n的约数求出（n除以约数）的欧拉函数的和即是答案。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 typedef long long ll;
 7 
 8 int euler_phi( int n )
 9 {
10     int ans = n;
11     for ( int i = 2; i * i <= n; i++ )
12     {
13         if ( n % i == 0 )
14         {
15             ans = ans / i * ( i - 1 );
16             do
17             {
18                 n = n / i;
19             }
20             while ( n % i == 0 );
21         }
22     }
23     if ( n > 1 )
24     {
25         ans = ans / n * ( n - 1 );
26     }
27     return ans;
28 }
29 
30 int main ()
31 {
32     int t;
33     scanf("%d", &t);
34     while ( t-- )
35     {
36         int a, m;
37         scanf("%d%d", &a, &m);
38         ll res = 0;
39         for ( int i = 1; i * i <= a; i++ )
40         {
41             if ( a % i ) continue;
42             if ( i >= m )
43             {
44                 res += euler_phi( a / i );
45             }
46             if ( i * i == a ) continue;
47             if ( a / i >= m )
48             {
49                 res += euler_phi( i );
50             }
51         }
52         printf("%I64d\n", res);
53     }
54     return 0;
55 }