数论 - 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的因数分解形式。

代码+部分注释：

#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;
}