《ACM数论方面十道基础题目详解.docx》由会员分享，可在线阅读，更多相关《ACM数论方面十道基础题目详解.docx（11页珍藏版）》请在三一文库上搜索。
1、1、 公约数和公倍数http:/ namespace std;inline int Gcd(int m,int n) /求最大公约数 if (m=0) return n; return Gcd(n%m,m);int main()int n,a,b,g;cinn;while(n-)cinab;g=Gcd(a,b);coutg a*b/gendl; 2、 Biorhythmshttp:/ int main()int n,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+=21
2、252;printf(%dn,n);3、 韩信点兵http:/ main() int a,b,c,n; scanf(%d%d%d,&a,&b,&c); for(n=11;n100;n+) if(n%3=a&n%5=b&n%7=c) printf(%dn,n); 中国剩余定理思路代码：#includeint main()int a,b,c,m;scanf(%d %d %d,&a,&b,&c);m=(70*a+21*b+15*c)%105;printf(%dn,m);return 0; 4、 次方求模http:/ (a(b/2)%c)%c比如我们要算325%4的值，由于25=1+8+16，那么我们
3、就只需要知道31,38,316的值。这样复杂度就从O(n)降低为O(log(n)了。代码实现如下：#include using namespace std;int mod(int k,int x,int c)int a=1;long long r=k;while(x)if(x&1)a=(a*r)%c;r=(r%c)*(r%c)%c;x=x1;return a;int main()int n,a,b,c;cinn;while(n-)cinabc;coutmod(a,b,c)endl; 5、 青蛙的约会 http:/poj.org/problem?id=1061这道题目用到了扩展欧几里德算法。设过
4、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 _int64 gcd(_int64 a,_int64 b) if(b=0) return a; return gcd(b,a%b);void exgcd(_int64 a,_int64 b,_int64 &m,_int64 &n) if(b=0) m=1; n=0; return ; exg
5、cd(b,a%b,m,n); _int64 t; t=m; m=n; n=t-a/b*n;int main() _int64 x,y,m,n,l,a,b,c,k1,k2,r,t; while(scanf(%I64d%I64d%I64d%I64d%I64d,&x,&y,&m,&n,&l)!=EOF) a=n-m; b=l; c=x-y; r=gcd(a,b); if(c%r) printf(Impossiblen); continue; a/=r; b/=r; c/=r; exgcd(a,b,k1,k2); t=c*k1/b;/注1 k1=c*k1-t*b; if(k10) k1+=b; pri
6、ntf(%I64dn,k1); return 0;6、 Least Common Multiplehttp:/ 2|_12_16_24_2| 6 8 12 2| 3 4 6 此时我们发现3 、4、 6是互质的，所以12、16、24的最小公倍数就是2*2*2*3*4*6=576当然这种方法的代码难度会略高于上一种思路。附上代码（第一种思路）：#include int gcd(int x,int y) return x?gcd(y%x,x):y;int main() int i,j,n,m,ret,tem; scanf(%d,&n); while(n-) scanf(%d,&m); scanf(%
7、d,&ret); m-; while(m-) scanf(%d,&tem); ret=ret/gcd(ret,tem)*tem; printf(%dn,ret); 7、 C Looooopshttp:/poj.org/problem?id=2115扩展欧几里德，不是太裸的题目：意思是输入4个数：a, b, c, k;(0=a, b, c2k, 1=k=32)计算是否存在x,使（a+c*x ) b(mod 2k)；如果存在输出x,否则输出FOREVER;思路：首先知道存在temp使(a+temp) b(mod 2k)；可得，temp = (b-a)%(2k);现在问题是计算是否存在x,使x*c
8、temp(mod 2k)；也就是求x*c-(x*c/(2k) * 2k = temp - (temp/2k) * 2k;既x*c-(x*c/(2k) - temp / (2k)*(2k) = temp;既x*c-y*(2k) = temp;因为c, k, temp都以知，（就是二元一次方程组（a*x0+b*y0=c的形式,知道如果（GCD(a, b)若不能整除c,可以判断方程无解）现在问题是计算x，计算gcd = gcd(c, 2k),先判断是否有解；若有解，方程两边除以gcd：因为gcd（c/gcd, 2k/gcd）= 1,所以用扩展欧几里德算法可求出：x0*(c/gcd) + y0*(2k
9、/gcd) = 1;因此两边乘以temp/gcd得x*(c/gcd) + y*(2k/gcd) = temp/gcd.此x就是满足题目（x*c temp(mod 2k)）的解。代码：#include long long extended_gcd(long long a, long long b, long long &x, long long &y) long long ret, tmp; if (!b) x = 1, y = 0; return a; ret = extended_gcd(b, a % b, x, y); tmp = x; x = y; y = tmp - a / b * y
10、; return ret;long long modular_linear_equation(long long a, long long b, long long n) long long x, y, e; long long d = extended_gcd(a, n, x, y); if (b % d) return -1; e = b / d * x % n + n; return e % (n / d);int main() long long a, b, c, ans; int k; while (scanf(%lld %lld %lld %d, &a, &b, &c, &k) =
11、 4) if (a = 0 & b = 0 & c = 0 & k = 0) break; ans = modular_linear_equation(c, b - a, 1LL n,(x-1)*m1，所以狼没办法遍历所有的洞，于是兔子躲过一劫！ 当n,m的最大公约数等于1，即互质，刚开始的证明同上，而k=1,说明狼可以遍历所有的洞，说得更白话点：只要洞口号是1的倍数，狼就可以进去。于是兔子就成了狼的美味了！代码：#includeint gcd(int y,int x)return x?gcd(x,y%x):y;int main()int m,n;while(scanf(%d%d,&m,&n)
12、!=EOF)if(gcd(m,n)=1)printf(NOn);elseprintf(YESn);9、 兔子的烦恼(二）http:/ gcd(int y,int x)return x?gcd(x,y%x):y;int main()int m,n,k,i;while(scanf(%d%d,&m,&n)!=EOF)if(gcd(m,n)=1)printf(NOn);elsek=gcd(m,n);printf(%d ,n-(n-1)/k-1);i=0;while(in)if(i%k)printf(%d ,i);+i;printf(n);10、A problem is easyhttp:/ 其中pi为
13、n的素因子。那么这个n的因子个数就是i=1k(ai+1)，利用这个结论这个题目就可以很快算出来了。代码如下（采用第一种思路）：#include #include int main()int i,j,k,l,m,n;scanf(%d,&m);while(m-)scanf(%d,&n);n=n+1;l=sqrt(double(n);for(i=2,k=0;i=l;i+)if(n%i=0)k+;printf(%dn,k); 采用第二种思路：#include #include #include int prime100006;int visit100006;int pos=0;int getprime
14、(int n) memset(visit,0,sizeof(visit); for(long long i=2;in;i+) if(!visiti) for(long long j=i*i;jn;j+=i) visitj=1; for(int i=2;in;i+) if(!visiti) primepos+=i; return pos;int getfs(int n) int ans=1; for(int i=0;ipos & primei*primei=n;i+) int d=0; while(n%primei = 0) d+; n/=primei; ans*=(d+1); if(n!=1) ans*=2; return ans;int main() getprime(100005); int t; scanf(%d,&t); while(t-) int n; scanf(%d,&n); printf(%dn,(getfs(n+1)-2+1)/2); /printf(%dn,(getfactionsum(n+1)-2+1)/2); return 0;