首页 > 代码库 > 数论基础题目八题【欧几里得】【筛法素数】【中国剩余定理】

数论基础题目八题【欧几里得】【筛法素数】【中国剩余定理】

之前看的数论的知识,现在做几道题目找找感觉.....


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的值即可。

扩展欧几里得,裸题,要是说难点在于之前的构造。