hdu 2841 Visible Trees

 1 /**
 2 大意： 求[1，m]， [1，n]  之间有多少个数互素。。。做了 1695 ，，这题就so easy 了
 3 **/
 4 #include <iostream>
 5 #include <cmath>
 6 #include <algorithm>
 7 using namespace std;
 8 const long long  maxn = 100050;
 9 long long phi[maxn];
10 long long priD[maxn];
11 int len ;
12 
13 void euler(long long  n){
14     long long  m = (int )sqrt(n+0.5);
15     len =0;
16     for(int i=2;i<=m;i++)if(n%i==0){
17         priD[len++] = i;
18         while(n%i==0)
19             n = n/i;
20     }
21     if(n>1)
22         priD[len++] = n;
23 }
24 
25 void phi_table(){
26     for(int i=2;i<maxn;i++)
27         phi[i] =0;
28     phi[1] =1;
29     for(int i=2;i<maxn;i++)if(!phi[i]){
30         for(int j=i;j<maxn;j+=i){
31             if(!phi[j]) phi[j] =j;
32             phi[j] = phi[j]/i*(i-1);
33         }
34     }
35 }
36 
37 long long solve(long long  m){
38     long long  sum = 0;
39     long long  flag,tmp;
40     for(int i=1;i<1ll<<len;i++){
41         tmp =1;
42         flag =0;
43         for(int j=0;j<len;j++){
44             if(i&(1ll<<j)){
45                 tmp *= priD[j];
46                 flag++;
47             }
48         }
49         if(flag%2)
50             sum += m/tmp;
51         else
52             sum -= m/tmp;
53     }
54     return sum;
55 }
56 
57 int main()
58 {
59     phi_table();
60     int t;
61     cin>>t;
62     long long  n,m;
63     while(t--){
64         cin>>m>>n;
65         if(m>n) //我们先默认 n > m， 不符合交换
66             swap(n,m);
67         long long sum =0;
68         for(int i=1;i<=m;i++)
69             sum += phi[i];
70         sum = sum*2-1;
71         for(int i=m+1;i<=n;i++){
72             euler(i);
73             sum += (m-solve(m));
74         }
75         cout<<sum<<endl;
76     }
77     return 0;
78 }