fork download
copy 
  1. #include<bits/stdc++.h>
  2. #pragma GCC optimize("O3,unroll-loops")
  3. #define maxn 1000005
  4. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  5. #define fi first
  6. #define se second
  7. #define maxb ((1<<8)+5)
  8. #define ll long long
  9. #define sti string
  10. #define int long long
  11.  
  12. using namespace std;
  13.  
  14. const int MAX=1e6;
  15. int prime[maxn];
  16. const int mod=1e9+7;
  17. vector<int> primes;
  18. int n,k,test;
  19.  
  20. void prepare(){
  21.    for(int i=2;i<=MAX;i++) prime[i]=1;
  22.    for(int i=2;i*i<=MAX;i++){
  23.       if(prime[i]){
  24.         for(int j=2*i;j<=MAX;j+=i) prime[j]=0;
  25.       }
  26.    }
  27.    for(int i=2;i<=MAX;i++) if(prime[i]) primes.push_back(i);
  28. }
  29.  
  30. int power(int a,int b){
  31.   int res=1;
  32.   while(b){
  33.      if(b&1) res=res*a%mod;
  34.      a=a*a%mod;
  35.      b>>=1;
  36.   }
  37.   return res;
  38. }
  39.  
  40. signed main() {
  41.     itachi
  42.     freopen("stablecomplex.inp","r",stdin);
  43.     freopen("stablecomplex.out","w",stdout);
  44.     prepare();
  45.     cin>>test;
  46.     while(test--){
  47.         cin>>n>>k;
  48.         if(k==1){
  49.             cout<<(power(2,n)-1+mod)%mod<<'\n';
  50.             continue;
  51.         }
  52.         vector<int> divi;
  53.         for(int x : primes){
  54.             if(k%x==0){
  55.                 int cur=1;
  56.                 while(k%x==0){
  57.                     cur*=x;
  58.                     k/=x;
  59.                 }
  60.                 divi.push_back(cur);
  61.             }
  62.         }
  63.         if(k>1) divi.push_back(k);
  64.         bool zero=0;
  65.         for(int x : divi){
  66.             if( x > n) {
  67.                 zero=1;
  68.                 break;
  69.             }
  70.         }
  71.         if(zero){
  72.             cout<<0<<'\n';
  73.             continue;
  74.         }
  75.         vector<int> Lcm(((1<<divi.size())+5),0);
  76.         vector<int> cnt(((1<<divi.size())+5),0);
  77.         Lcm[0]=1;
  78.         cnt[0]=n;
  79.         for(int mask=1;mask<(1<<divi.size());mask++){
  80.             int j=__builtin_ctz(mask);
  81.             if(Lcm[mask^(1<<j)] > n / divi[j]) Lcm[mask]=n+1;
  82.             else Lcm[mask]=Lcm[mask^(1<<j)]*divi[j];
  83.             cnt[mask]=n/Lcm[mask];
  84.         }
  85.  
  86.         for(int i=0;i<divi.size();i++){
  87.             for(int mask=0;mask<(1<<divi.size());mask++){
  88.                 if((mask>>i)&1){
  89.                     cnt[mask^(1<<i)] -= cnt[mask];
  90.                 }
  91.             }
  92.         }
  93.  
  94.         vector<int> num=cnt;
  95.         for(int i=0;i<divi.size();i++){
  96.             for(int mask=0;mask<(1<<divi.size());mask++){
  97.                 if((mask>>i)&1){
  98.                     num[mask] += num[mask^(1<<i)];
  99.                 }
  100.             }
  101.         }
  102.  
  103.         int res=0;
  104.         for(int mask=0;mask<(1<<divi.size());mask++){
  105.             int Count=power(2,num[mask]);
  106.             if((divi.size() - __builtin_popcountll(mask))%2==1){
  107.                 res=(res-Count+mod)%mod;
  108.             }
  109.             else res=(res+Count)%mod;
  110.         }
  111.         cout<<res<<'\n';
  112.     }
  113.     return 0;
  114. }
  115.  
Success #stdin #stdout 0.02s 12048KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/opPA5Z
language:
C++14 (gcc 8.3)
created:
3 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!