单变元模线性方程 入门指南

2019-04-13 14:54发布

站内文章 / 模拟电子
9735 0 1230
已知a、b、n，求x，使得ax≡b(mod n)。 令 d=gcd(a,n)，先使用扩展欧几里得求ax+ny=d的解。如果b不能整除d则无解，否则mod n意义下的解有d个，可以通过对某个解不断地加n/d得到。
POJ 2115 C Looooops
对于C的for(i=A ; i!=B ;i +=C)循环语句，问在k位存储系统中循环几次才会结束。 若在有限次内结束，则输出循环次数。 否则输出死循环。

#include #include #include using namespace std; typedef long long LL; typedef vector VL; LL extend_gcd(LL a,LL b,LL &x,LL &y){ if (b==0){ x=1;y=0; return a; } else{ LL r=extend_gcd(b,a%b,y,x); y=y-x*(a/b); return r; } } LL line_mod_equation(LL a,LL b,LL n){ LL x,y; LL d=extend_gcd(a,n,x,y); if (b%d==0){ x%=n; x+=n; x%=n; return x*(b/d)%(n/d); } else return -1; } int main() { int a,b,c,k; while (~scanf("%d%d%d%d",&a,&b,&c,&k)){ if (a==0&&b==0&&c==0&&k==0) break; LL m=1LL<

热门文章