首页 > 代码库 > 数论基础题目八题【欧几里得】【筛法素数】【中国剩余定理】
数论基础题目八题【欧几里得】【筛法素数】【中国剩余定理】
之前看的数论的知识,现在做几道题目找找感觉.....
poj 1061 传送门
题目大意,给你x,y,m,n,L。代表青蛙a的坐标x,青蛙b的坐标y,青蛙a一次跳的距离m,青蛙b一次跳的距离n,以及mod的值L,求经过多少次跳相遇。即求:(m-n)*x0=(x-y)(mod L); 模线性方程的解,不过要注意处理,因为(m-n)和(x-y)有可能是负的,如果(m-n)是负的,则直接对俩数取负数,下面就是对 ((x-y)+L)%L。
然后就能用modular_linear_equation(LL a,LL b,LL n)函数了。
代码
poj 2142 传送门
题目大意,给你abd是三个重量,ab是已知的重量,现在要求得出d,即m*a+n*b=d 求abs(m)+abs(n)的最大值,我们先用modular_linear_equation(LL a,LL b,LL n)函数得出一组特解,然后当m或者n最小的时候,得出响应的n或者m,求这两组中的最小值就是小的值了。
代码
poj 2689 传送门
题目详解
poj 2262 传送门
题目大意,任何一个偶数可以写成两个质数的和,给你一个100W以内的数c让你求出这个组合a+b=c,要求a尽量小,b尽量大。
100W的数据先打一个素数表就直接过了,裸题。
poj 1006 传送门
poj 2891 传送门
这中国剩余定理详见我的博客,后面有题解 中国剩余定理
HDU 1222 传送门
题解
题目大意,给出 m和n。一个数是0,每次加上m,然后mod n,问能不能将0~n-1这些数字走完。
也就是列出方程a*x=b(mod n) 当b=0,1,2,3,4....n-1的时候是否有解,其实是一个想法题,我们先来看看扩展欧几里得算法:
//ax=b(mod n) bool modular_linear_equation(LL a,LL b,LL n) { LL x,y,x0,i; LL d=ex_gcd(a,n,x,y); if(b%d!=0) return false; x0=x*(b/d)%n; //特解 for(i=1;i<d;i++) //解的个数是d printf("%d\n",(x0+i*(n/d))%n); return true; }其实也就是说当gcd(a*x,n)/ b!=0的时候无解b(0,1,2,3,4,...,n-1),也就是说gcd(a,n)==1的时候无解
HDU 1576 传送门
题解:传送门题目大意,给出n,B,(n=A%9973),求出(A/B)%9973的值。
n=A-A/9973*9973,A=Bx,Bx-A/9973*9973=n。即Bx-9973y=n。最后求出x%9973的值即可。
扩展欧几里得,裸题,要是说难点在于之前的构造。