fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N = 100001 , M = 1<<6 ;
  5. int bit[M] , cnt[M] , lst[M];
  6. int n , a , b ;
  7. ll lcm[M] , ans;
  8. vector<int>fct[N];
  9.  
  10. int main(){
  11.  
  12. for(int i=2;i+i<N;i++)
  13.     if( fct[i].empty() )
  14.         for(int j=i+i;j<N;j+=i)
  15.             fct[j].push_back(i);
  16.  
  17. for(int i=0;i<6;i++)
  18.     bit[1<<i]=i;
  19. for(int i=1;i<M;i++){
  20.     lst[i]=(i&-i);
  21.     cnt[i]=1+cnt[i-lst[i]];
  22.     }
  23.  
  24. int t;
  25. scanf("%d",&t);
  26. while( t-- ){
  27.         scanf("%d %d %d",&n,&a,&b);
  28.         if( a==0 ){
  29.             printf("1\n");
  30.             continue;
  31.         }
  32.         ans=2;
  33.         int c=0;
  34.         for(int d=2;d<=n;d++){
  35.             while( c+1<d && b*(c+1)<a*d )c++;
  36.             int sz = 1<<( (int)fct[d].size() );
  37.             int all = c;
  38.             lcm[0]=1;
  39.             for(int k=1;k<sz;k++){
  40.                     lcm[k] = lcm[ k - lst[k] ]*fct[d][ bit[ lst[k] ] ];
  41.                     if( cnt[k]&1 )
  42.                         all-= 1ll*c/lcm[k];
  43.                     else
  44.                         all+= 1ll*c/lcm[k];
  45.             }
  46.             ans+=all;
  47.         }
  48.         printf("%lld\n",ans);
  49. }
  50. return 0;
  51. }
  52.  
  53.  
Success #stdin #stdout 0.02s 8380KB
comments (?)
stdin
copy 
1
1 1 1
stdout
copy 
2
https://ideone.com/8VEAZd
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!