数论 - spoiler's Blog

hello kity

期待您的批阅，由于写解题报告时不一定考虑的很周到，所以如果您有什么不懂的地方，请您留言，然而一天之内我肯定会看见您信息，再对代码注释详细，让您更好的阅读

分类

HDU 1042（N！简单的大数问题）

题目分析：这个题目很简单，但是有点细节问题，我在代码里注释一下就可以了

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
    int i,j,n,t,lenth,carry,tempt;
     
    while(scanf("%d",&n)!=EOF){
        int s[7201]={1};
        lenth=1;
                 //lenth 记录数组的实际运用长度
        for(i=2;i<=n;i++){
            carry=0;
            for(j=0;j<lenth;j++){
                tempt=s[j]*i+carry;
                carry=tempt/100000;
                s[j]=tempt%100000;
            }
            while(carry){
                                                                    s[lenth++]=carry%100000;
                            //如果有进位 数组运用的实际长度+1
                carry/=100000;
            }
        }
        j=lenth-1;
        printf("%d",s[j--]);
                //注意看好这一步！最高位的前置0不能输出，其他的前
                  //置0要输出
        for(;j>=0;j--)
            printf("%05d",s[j]);
        printf("\n");
    }
    return 0;
}

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

Input

输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。

题目分析：首先青蛙A B 相遇必须满足：( x+ m*s ) - ( n*s + y ) = k*L; 这里 s 代表他们跳的步数，k代表他们在第几圈相遇！

这里如果你想尝试枚举的话，只能说这里的浮动性太大了，谁能确定 s 的范围呢，又有谁知道最小的 s 是多大呢，这个也许
会很大的！所以只能用扩展的欧几里德求这个不定方程！

求解不定方程： ( x+ m*s ) - ( n*s + y ) = k*L 首先我们把这个方程变形： s * ( n - m) + k* L = x -y ; 注意观察这个方程, 这就是所谓的线性同余方程，对于这种方程，如果有解必须满足（x - y）% gcd ( n-m, L )==0 不然就无解，输出Imposible！

这里通过看别人的总结与自己看书，介绍一下怎么用欧几里德扩展求不定方程：

设标准方程式为： a*x +b*y =d (a,b已知)

第一步：

首先求出gcd(a,b) ，然后化简方程，使得a/=gcd(a,b); b/=gcd(a,b); d/=gcd(a,b);

这样的话化简过后的 a,b就是互质的啦！（下面说的a,b 都是已经化简过的注意哦不再声明了）

第二步：

先求出 a*x+b*y=gcd(a,b) 的一组特解，也就是方程 a*x+b*y=1 的一个特解（a,b互质所以最大公约数为1！）

然后将特解（x0, y0）代入方程，并变形： a* x0 *d + b* y0 *d= d 再仔细看看， (x=x0*n ,y=y0*n) 这不是
第一步里面化简后的标准方程的一组解麽？然后我已经求得标准方程的一组解了，继续讨论解系里面的最小值吧！

第三步：

根据解系的公式： x =x1 + b* t ; y =y1 - a *t; 我们首先假设他最小的解x=0 ，然后求出此时的 t=-x1/b; 然后带入

求最小的解x=x1+b*t=x1 - b*t ;因为此时的t为负数，减去他的负数，就是等于加上他！

代码+部分注释：

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
long long gcd(long long a,long long b){
    long long c;
    if(a<b){
        c=a;    a=b;
        b=c;
    }
    while(b){
        c=b;
        b=a%b;
        a=c;
    }
    return a;
}
long long extended_gcd(long long a,long long b,long long &x,long long &y){
    long long ans,t;
    if(b==0){
        x=1;    y=0;
        return a;
    }
    else{
        ans=extended_gcd(b,a%b,x,y);
        t=x;    x=y;
        y=t-(a/b)*y;
    }
    return ans;
}
int main(){
    long long x,y,m,n,l;
    long long a,b,d,k,s,t;
    while(scanf("%lld %lld %lld %lld %lld",&x,&y,&m,&n,&l)!=EOF){
        a=n-m;
        b=l;
        d=x-y;
        long long r=gcd(a,b);
        if(d%r!=0){
            printf("Impossible\n");
            continue;
        }
        a/=r;
        b/=r;
        d/=r;
        extended_gcd(a,b,s,k);
        s=s*d;
        k=k*d;
        t=s/b;
        s=s-t*b;
        if(s<0)
            s+=b;
        printf("%lld\n",s);
    }
    return 0;
}

hit2813 Garden visiting 关于组合数的一个简单的拆分求解

题目大意：给你n * k 的矩形，始点在矩形的左上角，出口在矩形的右下角，求出最快走出这个矩阵的，方案数。

题目分析：最短的走出矩阵的方案的路程肯定是N+k，然后我们把这个路程离散化成N+K个状态，但是每种走法，的起点，跟终点的状态都一样的，只不过N+K-2里面有不同的走法，我们换位思考一下，在N+K-2个状态里有有K-1个状态分别投影在 K边的不同的点上面，因为，你必须往下移动K-1个单位才能到达出口，所以在竖直方向上必须有K-1个状态分别投影在K边的不同点上，这样我们就得出了方案数的组合数，就是在N+K-2里面选k-1个！公式： $C_{n+k-2}^{k-1}$

计算方面就是把这个组合数分别分解成素数，然后对素数进行求解，取模！

代码+部分注释：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int pri[20000],num[20000],cnt,p;
bool flag[200001];
void get_pri(){
    memset(flag,true,sizeof(flag));
    int i,j;
    pri[1]=2;
    cnt=1;
    for(i=4;i<=200000;i+=2)
        flag[i]=false;
    for(i=3;i<=3000;i+=2)
        for(j=i*i;j<=200000;j+=2*i)
            flag[j]=false;
    for(i=3;i<=200000;i+=2)
        if(flag[i])
            pri[++cnt]=i;
    return ;
}
int paw(int a,int t){
    int ans=1;
    while(t){
        if(t%2==1)
            ans=(ans*a)%p;
        a=(a*a)%p;
        t/=2;   
    }
    return ans;
}
int solve(){
    int cas,n,k,c,s,i;
    long long ans;
    scanf("%d",&cas);
    while(cas--){
        scanf("%d %d %d",&k,&n,&p);
        if(k>n){
            c=k;    k=n;
            n=c;
        }
        n=k+n-2;
        k--;
        if(k==n){
            printf("%d\n",1%p);
            continue;
        }
        for(i=1;i<=n&&pri[i]<=n;i++)
            num[i]=0;
        for(i=1;pri[i]<=n&&i<=cnt;i++){
            s=pri[i];
            while(n>=s){
                num[i]+=n/s-(n-k)/s-k/s;
                s*=pri[i];
            }
        }
        ans=1;
        for(i=1;i<=cnt&&pri[i]<=n;i++){
            if(num[i]>0)
                ans=(ans*paw(pri[i],num[i]))%p;
            if(ans==0)
                break;
        }
        printf("%lld\n",ans);
    }
    return 0;
}
int main(){
    get_pri();
    solve();
    return 0;
}

FOJ（1753 Another Easy Problem 又一种整数分解）

题目大意：就是给你多个组合数，让你求出

C(n1,m1)==0 (mod M)

C(n2,m2)==0 (mod M)

C(n3,m3)==0 (mod M)

的最大的M满足上式，

题目分析：

其实就是把这些组合数，分解成素数因子，然后求每个因子出现的最少的次数，题目不难但时间卡的好紧，我超时得想吐，如果您也遇到跟我一样的情况，请你细细看我代码提示的各个优化环节！不懂的留言，我们一起讨论

代码+部分注释：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int pri[1000011];
bool flag[1000001];
int sim[1000001];
int num1[151],num2[151];
int cnt;
void get_pri(){//生成素数表
    for(int i=1;i<=1000000;i++)
        flag[i]=true;
    pri[1]=2;
    cnt=1;
    flag[0]=flag[1]=false;
    for(int i=4;i<=1000000;i+=2)
        flag[i]=false;
    for(int i=3;i<3000;i+=2)
        for(int j=i*i;j<=1000000;j+=2*i)
            flag[j]=false;
    for(int i=3;i<=1000000;i+=2)
        if(flag[i])
            pri[++cnt]=i;
    return ;
}
int paw(int a,int t){
    int ans=1;
    while(t){
        if(t%2==1)
            ans=ans*a;
        a=a*a;
        t/=2;
    }
    return ans;
}
void solve(){
    int cas,n,k,i,s,j,t;
    bool flag;
    int maxn;
    while(scanf("%d",&cas)!=EOF){
        flag=false;
        maxn=0;
        for(i=1;i<=cas;i++){
            scanf("%d %d",&num1[i],&num2[i]);
            if(maxn<num1[i])
                maxn=num1[i];
            if(num1[i]==num2[i])
                flag=true;
                         //如果哦值为1的情况，就不用计算了，肯定就是1啦！
        }
        if(flag){
            printf("1\n");
            continue;
        }
        for(j=0;j<=100000;j++)
            sim[j]=2147483647;
        for(t=0;t<cas;t++){
            n=num1[t+1];
            k=num2[t+1];
            for(i=1;i<=cnt&&pri[i]<=maxn;i++){
                if(sim[i]==0)//这也是一个优化的地方，如果是0，
                                       //这个素数在各个组合数里出现的最少次数肯定是0啦
                    continue;
                int sum=0;
                int p=pri[i];
                while(n>=p){//这个就是计算各个素数在组合数里出现的次数
                    sum=sum+n/p-k/p-(n-k)/p;
                    p*=pri[i];
                                  //记得一次把这个写错了写成“p*=p”悲剧哦，段错误，肯定超出int范围啦！
                }
                if(sum<sim[i])
                    sim[i]=sum;
                             //sim[i]是记录第i个素数在各个组合数里出现的最少的素数！
            }   
        }
        long long ans=1;
                 //下面这个循环就无非是 计算每个组合数里，各个素数出现的最少次数，
               //组合成的数ans，也就是题目要求的数！
        for(i=1;i<=cnt&&pri[i]<=maxn;i++){
            if(sim[i]>0&&sim[i]!=2147483647){
                ans=ans*paw(pri[i],sim[i]);
            }
        }
        printf("%lld\n",ans);
    }
    return ;
}
int main(){
    get_pri();
    solve();
    return 0;
}

PKU （2992 Divisors 整数分解的经典应用！）

题目大意：就是给你一个组合数 $$C_n^k$$ 这里0=<k=<n=<341

题目分析：

1.约数个数定理：

设n的标准质因数分解为n=p1^a1*p2^a2*...*pm^am,

则n的因数个数=(a1+1)*(a2+1)*...*(am+1).

2. 对于任意质数p，n！中有（n/p+n/p^2+n/p^3+...)个质因子p。

代码+部分注释：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int pri[200];
bool flag[532];
int cnt;
void get_pri(){
    for(int i=1;i<=431;i++)
        flag[i]=true;
    pri[1]=2;
    cnt=1;
    flag[0]=flag[1]=false;
    for(int i=4;i<=431;i+=2)
        flag[i]=false;
    for(int i=3;i<23;i+=2)
        for(int j=i*i;j<=431;j+=2*i)
            flag[j]=false;
    for(int i=3;i<=431;i+=2)
        if(flag[i])
            pri[++cnt]=i;
    return ;
}
int main(){
    int n,k,s,i;
    int num[100];
    get_pri();
    while(scanf("%d %d",&n,&k)!=EOF){
        memset(num,0,sizeof(num));
        for(i=1;i<=cnt;i++){
            s=n;
            if(s<pri[i])
                break;
            while(s){
                num[i]+=s/pri[i];
                s/=pri[i];
            }
        }
        for(i=1;i<=cnt;i++){
            s=n-k;
            if(s<pri[i])
                break;
            while(s){
                num[i]-=s/pri[i];
                s/=pri[i];
            }
        }
        for(i=1;i<=cnt;i++){
            s=k;
            if(s<pri[i])
                break;
            while(s){
                num[i]-=s/pri[i];
                s/=pri[i];
            }
        }
        long long sum=1;
        for(i=1;i<=cnt;i++)
            if(num[i]>0)
                sum*=num[i]+1;
        printf("%lld\n",s);
    }
    return 0;
}

POJ （1811 Prime Test 关于miller_rabin的素数判断和pollard_rho的整数分解）

题目大意：就是给一个很大的数，让你判断是否为素数，如果不是则计算出小于等于他的最小的素数。2 <= N < 2⁵⁴

题目分析：这里由于数字非常大，我们不能按照常规思路来做，

miller_rabin的素数判断：Fermat小定理：若n为素数，则,有an-1≡1(mod n)，大部分的都满足 $2^{n-1}$ =1(mod n)，但是这不能包含所有情况，所以我们利用随机函数，来随机产生在2～n-2直接的数进行测试，如果没测出来，几乎就可以判断这个数是素数，这样做n太大了，计算起来肯定会超时的，要知道n的范围：2～2^54 这样太可怕了，这样的话我们来优化：

首先n-1= m*2^q ，2^(n-1)=(2^m)^2^q 在这里求m,与q应该是非常简单的事情吧，然后我们怎么办呢？这里我可以利用随机数a枚举

(2^m)^2^q （q=1..q-1），因为这些式子是 2^(n-1)的因数，如果他们不是素数，那么证明N不是素数，反之是素数（只是说概率很大可以看作是了），

这里还有一种情况，就是该数不是素数，然后就要分解整数，求出最小的一个素数，这里分解整数，用到的是pollard_rho分解法：

这里证明我就不写了，水平有限，只写过程：

首先我们用随机函数生成一个x1（1<x1<n）,然后根据x1 构造出x2 ( f[x]=x1^2+c )然后这里假设有p 能够整除 x1-x2 ，x1-x2=p*q,这里q显然可以整除x1-x2，但是x1-x2不能整除n，从而可以得到，q不能整除 n，所以gcd( (x1-x2) ,n )有可能得到1，也有可能得到n的一个因数，所以我们进行随机枚举，这样就可以计算出n的因数分解形式。

代码+部分注释：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

#include<iostream>
#include<cstdio>
#include<ctime>
 #include<cstdlib>
using namespace std;
long long top=0,pri[100];
long long multiply( long long a,long long b,long long n){
    long long exp,res=0;
        //这个就是用加法，来模拟乘法，为了防止运算的数太大，
    exp=a%n;
    while(b){
        if(b&1){
            res+=exp;
            if(res>n)
                res-=n;
        }
        exp<<=1;
        if(exp>n)
            exp-=n;
        b/=2;
    }
    return res;
}
long long paw(long long a,long long t,long long n){
    long long ans=1;
    a=a%n;
    while(t){
        if(t%2==1)
            ans=multiply(ans,a,n);  
        a=multiply(a,a,n);
        t/=2;
    }
    return ans;
}
long long gcd(long long a,long long b){
    long long c;
    if(a<b){
        c=a;
        a=b;    b=c;    
    }
    while(b){
        c=b;
        b=a%b;
        a=c;
    }
    return a;
}
bool miller_rabin(long long n,long long ti){
    if(n==2)
        return true;
    if(n<2||!(n&1))
        return false;
    long long p=n-1;
    long long k=0,a,x;
    while(p%2==0){
        p/=2;
        k++;
    }
    long long ans;
    srand(time(0));
    for(int t=1;t<=ti;t++){
        a=rand()%(n-1)+1;
        x=paw(a,p,n);
        for(int i=1;i<=k;i++){
            ans=multiply(x,x,n);
            if(ans==1&&x!=1&&x!=n-1)
                return false;
            x=ans;
        }
        if(ans!=1)
                //注意这个判断！
            return false;
    }
    return true;
}
long long pollard_rho(long long a,long long k,long long n){
    srand(time(0));
    long long x=rand()%(n-1)+1;
    long long i=1,t=2;
    long long y=x;
    while(1){
        i++;
        x=(multiply(x,x,n)+k)%n;
        long long ans=gcd(y-x,n);
        if(ans>1&&ans<n)
            return ans;
        if(x==y)
            return n;
        if(t==i){
            y=x;
            t*=2;
        }
    }
}
void search(long long n,long long k){
    if(miller_rabin(n,10)){
        pri[++top]=n;
        return ;
    }
    else{
        long long p=n;
        while(p>=n)
            p=pollard_rho(p,k--,n);
        search(p,k);
        search(n/p,k);
    }
}
int main(){
    int cas,i;
    long long n;
    cin>>cas;
    while(cas--){
        scanf("%lld",&n);
        if(miller_rabin(n,10ll))
            printf("Prime\n");
        else{   
            top=0;
            search(n,180);
            long long min=-1;
            for(i=1;i<=top;i++){
                if(min<0||min>pri[i])
                    min=pri[i];
            }
            printf("%lld\n",min);
        }
    }
    return 0;
}

ZOJ（2562 More Divisors 求反素数经典应用！）

题目大意：给一个N求不超过N的哪个数的因子数最多，数目相同的取值小的那个！

题目分析：这里引进反素数知识：

反素数第一点：g(x)表示 x含有因子的数目，设 0<i<=x 则g(i)<=x;

反素数第二个特性：2^t1*3^t2^5^t3*7^t4..... 这里有 t1>=t2>=t3>=t4...

所以我们根据这两个属性进行递归求解！

递归过程：

首先做出三条判断，第一是否该值不超过N的大小，第二比较因子的个数，更新最大的，即更新最大的反素数，第三如果因子数相等，则更新较小的。

然后枚举+递归不断尝试更新，使得得到因子数最大的那个！

代码+部分注释：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long bestres,bestsum,n;
long long pri[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
//res表示当前讨论的值，sum表示该值的因子数目，
//k表示讨论到第几个素数了，limit表示上次的幂的值
//这次幂的上限，就是体现t1>=t2>=t3...
void work(long long res, long long sum,int k,int limit ){
    if(res>n)//如果超过n就跳出！
        return ;
    if(sum>bestsum){
      //这次计算的因子数目比我以前过程的最大值还大，那么就要更新！
        bestres=res;
        bestsum=sum;
    }
    if(sum==bestsum&&res<bestres){
//如果因子数目一样，取值比较小的！
        bestres=res;
    }
    long long p=pri[k];
//记得第一次p=pri[k],因为下面i是从1开始计数的！
    for(int i=1;i<=limit;i++,p*=pri[k]){
        if(res*p>n)
            break;
        else
            work(res*p,sum*(i+1),k+1,i);
    }
}
int main(){
    while(scanf("%lld",&n)!=EOF){
        bestres=1LL;
        bestsum=1LL;
        work(1LL,1LL,0,50);
        printf("%lld\n",bestres);
    }
    return 0;
}

POJ (2262 Goldbach's Conjecture)

题目大意：给你一个大于等于6的偶数，让你求出两个奇素数，a,b 满足 x=a+b； a,b也许有多对，但是只需要求出 b-a最大的那对！

题目分析：这题直接暴力就可以了，先求出奇素数，第一队就是满足条件的了

代码：//pku 2909 pku2262 hdu1397 AC代码都差不多

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int s[500020];
int flag[1000002]={0};
void init(){
    int k=1;
    for(int i=2;i<=1000000;i+=2)
        flag[k]=1;//“0”代表是奇素数，”1“代表不是！
    for(int i=3;i<=1000000;i+=2){
        if(!flag[i]){
            s[k++]=i;
            for(int j=2*i;j<=1000000;j+=i)
                flag[j]=1;
        }   
    }
}
int main(){
    init();
     long n,i;
    while(scanf("%ld",&n),n){
        if(n%2==1)
            continue;
        long long p=n/2+1;
        for(i=1;s[i]<=p;i++){
            int k=n-s[i];
            if(!flag[k]){
                printf("%ld = %d + %d\n",n,s[i],k);
                          break;//注意第一对就是题目要的，这里要直接跳出了 不然TLE
            }
        }
        if(i>p)
            printf("Goldbach's conjecture is wrong.\n");//这里要不要无所谓 其实
    }
    return 0;
}

PKU (1730 Perfect Pth Powers)

题目分析：就是给你 X 求最大的p满足 X=a^p 特别提醒一下 X可正可负！

这里我用的是暴力，就是第一种枚举+二分，第二种是比较高效的暴力0MS过的！

这里唯一要考虑的是，首先如果是正值我们不用做任何处理，如果是负数，那么他的p肯定不能是偶数，如果是偶数，p次方后肯定是整数，所以会与答案有冲突，如果还有不懂的请您留言

代码

#include<stdio.h>
#include<cmath>
#include<iostream>
using namespace std;
int main()
{
  int i;
  double n;
  while(cin>>n,n){
         int maxn=1;
         bool flag=false;
         if(n<0){
               n*=-1;
               flag=true;        
         }
        for(i=32;i>=1;i--){
              double up=ceil(pow(n,1.0/i));
              double down=floor(pow(n,1.0/i));
              if(fabs(n-pow(up,i))<1e-8||fabs(n-pow(down,i))<1e-8) {
                         if(flag){
                                  if(i%2==1){
                                            maxn=i;  break;
                                  }    
                          }    
                          else {
                                maxn=i;
                                break;
                               }                                                 
              }                                
        }
         printf("%d\n",maxn);                       
  }
 return 0;
}

#include<stdio.h>
#include<cmath>
#include<iostream>
using namespace std;
int main()
{
  long long n,i,t,maxn;
  while(cin>>n,n){
         maxn=0;
         bool flag=false;
         if(n<0){
               n*=-1;
               flag=true;        
         }
         long long k=(long long)sqrt(n);
         for(i=2;i<=k;i++){
             long long m=n;
             t=0;
             while(m%i==0){
                    t++;
                    m/=i;            
             } 
             if(m==1){
                      if(flag){
                           if(t%2==1)
                                     maxn=maxn>t? maxn:t;    
                           else
                                     continue;              
                      }
                     else
                          maxn=maxn>t? maxn:t;         
             }               
         } 
         if(maxn==0)
                    maxn=1;
         printf("%lld\n",maxn);                       
  }
 return 0;
}

PKU( 2191 Mersenne Composite Numbers )

题目大意：

就是求梅森组合数!

这题网上都是打表算出来的，在这里我先贴一下我的打表过的，这根本不算是我写的，因为这个表不是我自己计算出来的，我表示心里很无助~代码贴完，再次保证随后肯定附上我详细的解答过程，不用打表的，我去膜拜大牛的思路！

#include<stdio.h>
int main()
{
 int n,i;
 int b[10]={11,23,29,37,41,43,47,53,59};
char a1[10][100] ={"23 * 89 = 2047 = ( 2 ^ 11 ) - 1",
"47 * 178481 = 8388607 = ( 2 ^ 23 ) - 1",
"233 * 1103 * 2089 = 536870911 = ( 2 ^ 29 ) - 1",
"223 * 616318177 = 137438953471 = ( 2 ^ 37 ) - 1",
"13367 * 164511353 = 2199023255551 = ( 2 ^ 41 ) - 1",
"431 * 9719 * 2099863 = 8796093022207 = ( 2 ^ 43 ) - 1",
"2351 * 4513 * 13264529 = 140737488355327 = ( 2 ^ 47 ) - 1",
"6361 * 69431 * 20394401 = 9007199254740991 = ( 2 ^ 53 ) - 1",
"179951 * 3203431780337 = 576460752303423487 = ( 2 ^ 59 ) - 1"};
 scanf("%d",&n);
 for(i=0;i<9;i++)
 {
    if(n>b[i])
    printf("%s\n",a1[i]);
    else break;
  }
 return 0;
}