HDU2841 Visible Trees（容斥原理）

  1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);
  2 #include <cstdio>//sprintf islower isupper
  3 #include <cstdlib>//malloc  exit strcat itoa system("cls")
  4 #include <iostream>//pair
  5 #include <fstream>//freopen("C:\\Users\\13606\\Desktop\\Input.txt","r",stdin);
  6 #include <bitset>
  7 //#include <map>
  8 //#include<unordered_map>       HDU2841
  9 #include <vector>
 10 #include <stack>
 11 #include <set>
 12 #include <string.h>//strstr substr strcat
 13 #include <string>
 14 #include <time.h>// srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
 15 #include <cmath>
 16 #include <deque>
 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
 18 #include <vector>//emplace_back
 19 //#include <math.h>
 20 #include <cassert>
 21 #include <iomanip>
 22 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
 23 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
 24 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
 25 //******************
 26 clock_t __START,__END;
 27 double __TOTALTIME;
 28 void _MS(){__START=clock();}
 29 void _ME(){__END=clock();__TOTALTIME=(double)(__END-__START)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}
 30 //***********************
 31 #define rint register int
 32 #define fo(a,b,c) for(rint a=b;a<=c;++a)
 33 #define fr(a,b,c) for(rint a=b;a>=c;--a)
 34 #define mem(a,b) memset(a,b,sizeof(a))
 35 #define pr printf
 36 #define sc scanf
 37 
 38 #define ls rt<<1
 39 #define rs rt<<1|1
 40 typedef pair<int,int> PII;
 41 typedef vector<int> VI;
 42 typedef unsigned long long ull;
 43 typedef long long ll;
 44 typedef double db;
 45 const db E=2.718281828;
 46 const db PI=acos(-1.0);
 47 const ll INF=(1LL<<60);
 48 const int inf=(1<<30);
 49 const db ESP=1e-9;
 50 const int mod=(int)1e9+7;
 51 #define int ll
 52 const int N=(int)1e6+10;
 53 
 54 int pri[50],num;
 55 void getpri(int n)
 56 {
 57     num=0;
 58     for(int i=2;i*i<=n;++i)
 59     {
 60         if(n%i)continue;
 61         while(n%i==0)n/=i;
 62         pri[++num]=i;
 63     }
 64     if(n>1)
 65         pri[++num]=n;
 66 }
 67 
 68 int getnocoprime(int x)
 69 {
 70     int ans=0;
 71     int tot=(1<<num)-1;
 72     for(int i=1;i<=tot;++i)
 73     {
 74         int sum=0;
 75         int temp=1;
 76         for(int j=0;j<=num-1;++j)
 77         {
 78             if((i>>j)&1)
 79                 sum++,temp*=pri[j+1];
 80         }
 81         if(sum&1)
 82             ans+=x/temp;
 83         else
 84             ans-=x/temp;
 85     }
 86     return ans;
 87 }
 88 
 89 void solve()
 90 {
 91     int n,m;
 92     sc("%lld%lld",&n,&m);
 93     int ans=0;
 94     for(int i=1;i<=n;++i)
 95     {
 96         getpri(i);
 97         ans+=m-getnocoprime(m);
 98     }
 99     pr("%lld\n",ans);
100 }
101 
102 signed main()
103 {
104     int T;
105     sc("%lld",&T);
106     while(T--)solve();
107     return 0;
108 }
109 
110 /**************************************************************************************/