资源描述：
《acm必做50题的解题-数论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、poj1061青蛙的约会这题用的是解线性同余方程的方法，之前没接触到过，搜索资料后看到一个人的博客里面讲的很好就拷贝过来了。内容如下：对于方程：ax≡b(modm)，a，b，m都是整数，求解x的值，这个就是线性同余方程。符号说明：mod表示：取模运算ax≡b(modm)表示：(ax-b)modm=0，即同余gcd(a,b)表示：a和b的最大公约数求解ax≡b(modn)的原理：对于方程ax≡b(modn)，存在ax+by=gcd(a,b)，x，y是整数。而ax≡b(modn)的解可以由x，y来堆砌。具体做法如下：第一个问题：求解gcd(a,b)定理一：gcd(
2、a,b)=gcd(b,amodb)欧几里德算法intEuclid(inta,intb){if(b==0)returna;elsereturnEuclid(b,mod(a,b));}附：取模运算intmod(inta,intb){if(a>=0)returna%b;elsereturna%b+b;}第二个问题：求解ax+by=gcd(a,b)定理二：ax+by=gcd(a,b)=gcd(b,amodb)=b*x'+(amodb)*y'=b*x'+(a-a/b*b)*y'=a*y'+b*(x'-a/b*y')=a*x+b*y则：x=y'y=x'-a/b*y'以上内
3、容转自hi.baidu.com/redcastle/blog/item/934b232dbc40d336349bf7e4.html由这个可以得出扩展的欧几里德算法：intexGcd(inta,intb,int&x,int&y){if(b==0){x=1;y=0;returna;}intr=exGcd(b,a%b,x,y);intt=x;x=y;y=t-a/b*y;returnr;}代码：#include#include#include#includeusingnamespacestd;__i
4、nt64mm,nn,xx,yy,l;__int64c,d,x,y;__int64modd(__int64a,__int64b){if(a>=0)returna%b;elsereturna%b+b;}__int64exGcd(__int64a,__int64b){if(b==0){x=1;y=0;returna;}__int64r=exGcd(b,a%b);__int64t=x;x=y;y=t-a/b*y;returnr;}intmain(){scanf("%I64d%I64d%I64d%I64d%I64d",&xx,&yy,&mm,&nn,&l);if(mm>
5、nn)//分情况{d=exGcd(mm-nn,l);c=yy-xx;}else{d=exGcd(nn-mm,l);c=xx-yy;}if(c%d!=0){printf("Impossible");return0;}l=l/d;x=modd(x*c/d,l);///取模函数要注意printf("%I64d",x);system("pause");return0;}POJ1142SmithNumber题意：寻找最接近而且大于给定的数字的SmithNumber什么是SmithNumber？用sum(int)表示一个int的各位的和，那一个数i如果是Smith
6、Number,则sum（i）=sigma(sum(Pj)),Pj表示i的第j个质因数。例如4937775=3*5*5*65837，4+9+3+7+7+7+5=42，3+5+5+（6+5+8+3+7）=42，所以4937775是SmithNumber。思路：要寻找大于给定数字且最接近给定数字的SmithNumber，只要将给定数字不断的加1，判断它是否是SmithNumber就行了，如果是SmithNumber就立即输出。但是如何判断是否是SmithNumber呢？首先就是要对数字进行质因数分解。质因数分解要保证因子都是质数。这里先介绍一个如何判断一个数int是
7、否是质数呢，如果对于这个数，i=2.....sqrt(int)都不是它的约数，那int就是一个质数。所以我们可以将i初始化为2，然后不断递增i，看i是否是int的一个约数，如果是的话那i就是int的一个质因数（因为这个数是从2开始第一个可以整除int的数，它不可能是一个可以分解的合数，否则，它的约数在它之前就整除int），然后将int除以该质因数，重置i为2，重新对int判断它是否是质数。这样最后剩下的int一定是一个质数，从而对int进行了质因数分解然后就很简单的将数字各质因数的各位加起来，看和是否等于该数字的各位和，如果相等那它可能就是SmithNumbe
8、r，为什么说只是可能呢，因为这个数可能
