fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long bs(vector<long long>&P,long long l){
  5. int s=0,e=P.size()-1;
  6. int m=(s+e)/2;
  7.  
  8. while(s<e){
  9. if((e-s)==1)break;
  10.  
  11. if(P[m]<l){
  12. s=m;
  13. m=(s+e)/2;
  14. }
  15. else{
  16. e=m;
  17. m=(s+e)/2;
  18. }
  19. }
  20. return P[e];
  21. }
  22.  
  23. int main(){
  24.  
  25.  
  26. long long temp=1;
  27. vector<long long>P;
  28. map<long long,int>Q;
  29. P.push_back(1);
  30. int c=1;
  31. Q[temp]=c;
  32. while(temp<=1e13){
  33. long long z=floor(sqrt(c));
  34. z*=c;
  35. z+=((c+1)/2);
  36. temp+=z;
  37. c++;
  38. P.push_back(temp);
  39. Q[temp]=c;
  40. }
  41.  
  42. int t;
  43. cin>>t;
  44.  
  45. while(t--){
  46. long long l,r;
  47. cin>>l>>r;
  48.  
  49. if((Q[l] && Q[r])){
  50. int ans=(Q[r]-Q[l])+1;
  51. cout<<ans<<endl;
  52. continue;
  53. }
  54.  
  55. int z1;
  56. if(Q[l]){
  57. z1=Q[l];
  58. }
  59. else{
  60. long long zz=bs(P,l);
  61. //cout<<zz<<" check ";
  62. z1=Q[zz]-1;
  63. }
  64.  
  65. int z2;
  66. if(Q[r]){
  67. z2=Q[r];
  68. //cout<<z2<<" check 2"<<endl;
  69. }
  70. else{
  71. long long zz=bs(P,r);
  72. z2=Q[zz]-1;
  73. }
  74.  
  75. int ans=(z2-z1)+1;
  76. cout<<ans<<endl;
  77.  
  78. }
  79.  
  80.  
  81. }
Success #stdin #stdout 0.07s 19260KB
stdin
1
2 6
stdout
3