fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.  
  6.  
  7.     long long temp=1;
  8.     set<long long>P;
  9.     map<long long,int>Q;
  10.     P.insert(1);
  11.     int c=1;
  12.     Q[temp]=c;
  13.     while(temp<1e13){
  14.         long long z=floor(sqrt(c));
  15.         z*=c;
  16.         z+=((c+1)/2);
  17.         temp+=z;
  18.         c++;
  19.         P.insert(temp);
  20.         Q[temp]=c;
  21.     }
  22.  
  23.     int t;
  24.     cin>>t;
  25.  
  26.     while(t--){
  27.         long long l,r;
  28.         cin>>l>>r;
  29.  
  30.         if((Q[l] && Q[r])){
  31.             int ans=(Q[r]-Q[l])+1;
  32.             cout<<ans<<endl;
  33.             continue;
  34.         }
  35.         auto it=lower_bound(P.begin(),P.end(),l);
  36.         long long temp=*it;
  37.  
  38.         auto it2=lower_bound(P.begin(),P.end(),r);
  39.         long long temp2=*it2;
  40.  
  41.         int z1=Q[temp];
  42.         if(temp>l){
  43.           z1--;
  44.         }
  45.  
  46.         int z2=Q[temp2];
  47.         if(temp2>r){
  48.             z2--;
  49.         }
  50.          int ans=(z2-z1)+1;
  51.          cout<<ans<<endl;
  52.  
  53.     }
  54.  
  55.  
  56. }
Success #stdin #stdout 0.11s 28684KB
comments (?)
stdin
copy 
1
2 19
stdout
copy 
4
https://ideone.com/l0Ydlq
language:
C++14 (gcc 8.3)
created:
2 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!