HDU 2841 Visible Trees

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 200010;
 5 vector<int>g[maxn];
 6 void init(){
 7     for(int i = 2; i < maxn; ++i){
 8         for(int j = 1; i*j < maxn; ++j)
 9             g[i*j].push_back(i);
10     }
11 }
12 int main(){
13     int kase,n,m;
14     init();
15     scanf("%d",&kase);
16     while(kase--){
17         scanf("%d%d",&n,&m);
18         LL ret = 0;
19         for(int i = 2; i <= n; ++i){
20             int cnt = 0,ans = 0;
21             for(int j = 1,t = g[i].size();j < (1<<t); ++j){
22                  LL tmp = 1;
23                  for(int k = cnt = 0; k < t; ++k){
24                     if((j>>k)&1){
25                         cnt++;
26                         tmp *= g[i][k];
27                     }
28                 }
29                 if(cnt&1) ans += m/tmp;
30                 else ans -= m/tmp;
31             }
32             ret += m - ans;
33         }
34         printf("%I64d\n",ret + m);
35     }
36     return 0;
37 }