acm数论方面十道基础题目详解

《acm数论方面十道基础题目详解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、公约数和公倍数http://acm.nyist.net/JudgeOnline/problem.php?pid=40这道题目是非常基础的题目，在学习了欧几里德算法之后，应该很好就能做的出来了。注意两个数的最小公倍数和最大公约数之间有关系为：a*b=gcd(a,b)*lcm(a,b);代码如下：#includeusingnamespacestd;inlineintGcd(intm,intn)//求最大公约数{if(m==0)returnn;returnGcd(n%m,m);}intmain(){intn,a,b,g;cin>>n;while(n--){cin>>a>>b;

2、g=Gcd(a,b);cout<

3、33==0&&k3%23==0&&k3%28==1则n=k2*p+k3*e+k1*i+k*21252；代码如下：#includeintmain(){intn,a,b,c,t;while(scanf("%d%d%d%d",&a,&b,&c,&t),~a){n=(5544*a+14421*b+1288*c)%21252-t;if(n<=0)n+=21252;printf("%d",n);}}1、韩信点兵http://acm.nyist.net/JudgeOnline/problem.php?pid=34这个题目也是很经典的中国剩余问题类的题目，思路跟上面差不多这道题目因为数据

4、范围很小实际上暴力就可以过，但是这个题目不失为练习中国剩余的很好题目，所以建议大家用中国剩余定理做一下。直接给出代码：暴力求解代码：#includemain(){inta,b,c,n;scanf("%d%d%d",&a,&b,&c);for(n=11;n<100;n++)if(n%3==a&&n%5==b&&n%7==c)printf("%d",n);}中国剩余定理思路代码：#includeintmain(){inta,b,c,m;scanf("%d%d%d",&a,&b,&c);m=(70*a+21*b+15*c)%105;printf("%d",

5、m);return0;}1、次方求模http://acm.nyist.net/JudgeOnline/problem.php?pid=102这个题目是要求出a的b次方对c取余的值。显然我们不能求出a^b后再对c取余，a^b可能是一个很大的数，而且这样做肯定很慢。那么我们利用同余定理来解决这个问题。当然最简单的我们会想到：a^b%c=((a^(b-1)%c)*(a%c))%c；但是这样效率依然是很低的。那么我们考虑一种叫做二分快速幂的思路。关键改进就是：a^b%c=((a^(b/2)%c)*(a^(b/2)%c))%c比如我们要算3^25%4的值，由于25=1+8+16，那么我们就只需要知道3^

6、1,3^8,3^16的值。这样复杂度就从O(n)降低为O(log(n))了。代码实现如下：#includeusingnamespacestd;intmod(intk,intx,intc){inta=1;longlongr=k;while(x){if(x&1)a=(a*r)%c;r=((r%c)*(r%c))%c;x=x>>1;}returna;}intmain(){intn,a,b,c;cin>>n;while(n--){cin>>a>>b>>c;cout<

7、题目用到了扩展欧几里德算法。设过s步后两青蛙相遇，则必满足以下等式：(x+m*s)-(y+n*s)=k*l(k=0,1,2....)稍微变一下形得：(n-m)*s+k*l=x-y令n-m=a,k=b,x-y=c,即a*s+b*l=c只要上式存在整数解，则两青蛙能相遇，否则不能。这样问题就转化为了扩展欧几里德问题了。代码如下：#include__int64gcd(__int64a,