fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long INF=1e18;
  4. const int MX=1e5+42;
  5. bool prime[MX];
  6. int mu[MX];
  7. void init()
  8. {
  9.     prime[1]=1;
  10.     for(int i=2;i*i<MX;i++)
  11.         if(prime[i]==0)
  12.         {
  13.             for(int j=i*i;j<MX;j=j+i) prime[j]=1;
  14.         }
  15.     for(int i=1;i<MX;i++) mu[i]=1;
  16.     for(int p=1;p<MX;p++)
  17.         if(prime[p]==0)
  18.         {
  19.             for(int i=p;i<MX;i=i+p) mu[i]=-mu[i];
  20.             if(1LL*p*p<MX)
  21.             {
  22.                 for(int j=p*p;j<MX;j=j+p*p) mu[j]=0;
  23.             }
  24.         }
  25. }
  26. long long n,x,y;
  27. const int BITS=16,SUB=(1<<BITS)-1;
  28. long long eval(long long x_,long long y_)
  29. {
  30.     long long y1=y_>>BITS;
  31.     long long y2=y_&SUB;
  32.     pair<long long,long long> ret={x_*y1/(x_+y_),x_*y1%(x_+y_)};
  33.     ret.first=ret.first<<BITS;
  34.     ret.second=ret.second<<BITS;
  35.     ret.second+=x_*y2;
  36.     ret.first+=ret.second/(x_+y_);
  37.     return ret.first;
  38. }
  39. vector<long long> compressed(long long n_,long long x_,long long y_)
  40. {
  41.     n_=min(n_,eval(x_,y_));
  42.     return {n_,x_,y_};
  43. }
  44. long long go_n(long long n_,long long b1,long long from,long long to)
  45. {
  46.     n_=n_/b1;
  47.     to=min(to,n_);
  48.     long long ret=0;
  49.     while(from<=to)
  50.     {
  51.         long long cur=n_/from;
  52.         long long to_cur=min(n_/cur,to);
  53.         ret+=cur*(to_cur-from+1);
  54.         from=to_cur+1;
  55.     }
  56.     return ret;
  57. }
  58. long long go_y(long long y_,long long b1,long long to)
  59. {
  60.     return go_n(y_,b1,b1+1,b1+to);
  61. }
  62. long long go_x(long long x_,long long b1,long long from)
  63. {
  64.     long long ret=0;
  65.     while(1)
  66.     {
  67.         long long c=x_/from/(from+b1);
  68.         if(c==0)break;
  69.         long long to=(-b1+sqrt(1LL*b1*b1+4*x_/c))/2;
  70.         ret+=(to-from+1)*c;
  71.         from=to+1;
  72.     }
  73.     return ret;
  74. }
  75. long long h_fast(long long n_,long long x_,long long y_)
  76. {
  77.     vector<long long> given=compressed(n_,x_,y_);
  78.     n_=given[0];
  79.     x_=given[1];
  80.     y_=given[2];
  81.     if(n_<=0)return 0;
  82.     long long ret=0;
  83.     for(long long b1=1;b1*b1<=y_;b1++)
  84.     {
  85.         long long to_y=(1LL*n_*b1-1)/(y_-n_);
  86.         long long from_x=(1LL*(x_-n_)*b1+n_)/n_;
  87.         ret+=go_y(y_,b1,to_y);
  88.         ret+=go_x(x_,b1,from_x);
  89.         ret+=go_n(n_,b1,to_y+1,from_x-1);
  90.     }
  91.     return ret;
  92. }
  93. long long fast_opt()
  94. {
  95.     long long res=0;
  96.     for(long long i=1;i*i<=n;i++)
  97.     {
  98.         vector<long long> given=compressed(n/i/i,x/i/i,y/i/i);
  99.         if(given[0]==0)break;
  100.         long long coeff=0,j=i;
  101.         while(compressed(n/j/j,x/j/j,y/j/j)==given)
  102.         {
  103.             coeff+=mu[j];
  104.             j++;
  105.         }
  106.         j--;
  107.         i=j;
  108.         if(coeff==0)continue;
  109.         long long cur=h_fast(n/i/i,x/i/i,y/i/i);
  110.         res+=coeff*cur;
  111.     }
  112.     return res;
  113. }
  114. int main()
  115. {
  116.     init();
  117.     cin >> n >> x >> y;
  118.     if(x>y)swap(x,y);
  119.     long long res=fast_opt();
  120.     cout << res;
  121.     return 0;
  122. }
  123.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VV0Qhl
language:
C++14 (gcc 8.3)
created:
177 days 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!