BJFU fudq的等式

  1 /*
  2  BJFU fudq的等式
  3  http://101.200.220.237/contest/19/problem/118/
  4  数论 勒让德定理 二分答案
  5  */
  6 #include <cstdio>
  7 #include <algorithm>
  8 #include <cstring>
  9 #include <cmath>
 10 #include <vector>
 11 #include <queue>
 12 //#define test
 13 using namespace std;
 14 const int Nmax=1000005;
 15 const long long INF=100000000000005LL;
 16 long long p[Nmax];
 17 long long times[Nmax];
 18 int cnt;
 19 long long n,x,y;
 20 
 21 long long Legendre(long long n,long long p,long long y)
 22 {
 23     long long ans=0LL;
 24     while(n>0)
 25     {
 26         ans+=n/p;
 27         if(ans>y)
 28             return y+1LL;
 29         n/=p;
 30     }
 31     return ans;
 32 }
 33 
 34 int is(long long n)
 35 {
 36     for(int i=1;i<=cnt;i++)
 37     {
 38         if(Legendre(n,p[i],times[i]*y)<times[i]*y)
 39             return 0;
 40     }
 41     return 1;
 42 }
 43 long long get()
 44 {
 45     long long n=0LL;
 46     long long l=1LL,r=INF;
 47     while(l<r)
 48     {
 49         long long mid=(l+r)>>1;
 50         long long m=is(mid);
 51         //printf("l:%lld r:%lld mid:%lld x:%lld y:%lld num:%lld
",l,r,mid,x,y,m);
 52         if(!m)
 53             l=mid+1;
 54         else 
 55             r=mid-1;
 56     }
 57     if(n==0LL && !is(r))
 58         n=r+1;
 59     else if(n==0LL && is(r))
 60         n=r;
 61     return n;
 62 
 63 }
 64 //long long get()
 65 //{
 66     //long long m=-1LL;
 67     //for(int i=1;i<=cnt;i++)
 68     //{
 69        //m=max(m,get(p[i],times[i]*y)); 
 70     //}
 71     //return m;
 72 //}
 73 int main()
 74 {
 75     #ifdef test
 76     #endif
 77     //freopen("test.in","r",stdin);
 78     while(scanf("%lld%lld",&x,&y)==2)
 79     {
 80         cnt=0;
 81         for(int i=2;i*i<=x;i++)
 82         {
 83             if(x%i==0)
 84             {
 85                 p[++cnt]=i;
 86                 times[cnt]=0;
 87                 while(x%i==0)
 88                 {
 89                     x/=i;
 90                     times[cnt]++;
 91                 }
 92             }
 93         }
 94         if(x!=1)
 95         {
 96             p[++cnt]=x;
 97             times[cnt]=1;
 98         }
 99 
100         if(cnt==0)
101         {
102             //printf("error
");
103             printf("0
");
104             continue;
105         }
106         printf("%lld
",get());
107     }
108     return 0;
109 }