fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. unsigned long long int dp[65][65]={0};
  4. int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61};
  5. unsigned long long int solve(unsigned long long int a){
  6.     bool bin[64]={0};
  7.     int i;
  8.     int itr=0;
  9.     unsigned long long int tempo=a;
  10.     while(tempo){
  11.         if(tempo&1){
  12.             bin[itr]=1;
  13.         }
  14.         itr++;
  15.         tempo>>=1;
  16.     }
  17.     int cnt1=0;
  18.     unsigned long long int ans=0;
  19.     int l=itr,itr2;
  20.     itr--;
  21.     while(itr>=0){
  22.         if(bin[itr]){
  23.             for(itr2=0;itr2<18;itr2++){
  24.                 int k=p[itr2]-cnt1;
  25.                 if(k>=0){
  26.                     ans+=dp[itr][k];
  27.                 }
  28.                 if(k>=itr)break;
  29.             }
  30.             cnt1++;
  31.         }
  32.         itr--;
  33.     }
  34.     return ans;
  35. }
  36. int main(){
  37.     int t,i,j;
  38.     cin>>t;
  39.     dp[0][0]=1;
  40.     for(i=1;i<65;i++){
  41.         dp[i][0]=1;
  42.         dp[i][i]=1;
  43.         for(j=1;j<i;j++)dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
  44.     }
  45.     unsigned long long int a,b,temp,ansa,ansb,anst;
  46.     while(t--){
  47.         cin>>a>>b;
  48.         ansa=solve(a);
  49.         ansb=solve(b);
  50.         anst=ansb-ansa;
  51.         bitset<64>foo(b);
  52.         int cnt=foo.count();
  53.         /*int cnt=0;
  54.         while(b){
  55.             if(b&1)cnt++;
  56.             b>>=1;
  57.         }*/
  58.         int itr2;
  59.         for(itr2=0;itr2<18;itr2++){
  60.             if(p[itr2]==cnt){
  61.                 anst++;
  62.                 break;
  63.             }
  64.         }
  65.         cout<<anst<<"\n";
  66.     }
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0s 3332KB
comments (?)
stdin
copy 
1
234 123456789123456789
stdout
copy 
29516597280498023
https://ideone.com/4Yamhz
language:
C++ (gcc 8.3)
created:
11 years 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!