扩展欧几里得，逆元初识(poj 1061+codeforce 7C line+hdu 1576 A/B)

扩展欧几里得，逆元初识(poj 1061+codeforce 7C line+hdu 1576 A/B)

poj 1061 青蛙的约会：

#include #include#define LL long longusing namespace std;LL gcd(LL a, LL b){ return b?gcd(b,a%b):a;}void extend_Euclid(LL a,LL b,LL &x,LL &y){if(b == 0) { x = 1; y = 0; return ;}extend_Euclid(b,a%b,x,y);LL tmp = x; x = y;y = tmp - (a / b) * y;}LL res(int a,int b){ while(a<0){ if(b<0)a-=b; else a+=b; } return a;}int main(){ LL x,y,m,n,L; LL a,b,c,xi,yi; while(~scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L)){ a=m-n; b=L; c=y-x; LL d=gcd(a,b); if(c%d!=0){ cout<<"Impossible\n"; continue; } a/=d; b/=d; c/=d; extend_Euclid(a,b,xi,yi); xi=(xi*c)%b; //通解x不会比L长，所以要提前mod(b). xi=res(xi,b); cout<

codeforce 7C line:

题意：判断一个线性方程组Ax+By+C=0是否有整数解，如果有，则输出整数解，否则输出-1.

并非是需要x一定要>0，利用扩展欧几里得求得x0,y0后再乘以相关倍数（-C/d)即可  [ d=gcd(A,B) ].

#include #include#include#define LL long long#includeusing namespace std;void extend_Euclid(LL a,LL b,LL &f,LL &x,LL &y){if(b == 0) { x = 1; y = 0; f=a; return ;}extend_Euclid(b,a%b,f,x,y);LL tmp = x;x = y;y = tmp - (a / b) * y;}int main(){ LL A,B,C,f,x,y; while(cin>>A>>B>>C){ extend_Euclid(A,B,f,x,y); if(C%f!=0){ cout<<"-1\n"; continue; } cout<

hdu 1576 A/B

题意：要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。数据的第一行是一个T，表示有T组数据。 每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。对应每组数据输出(A/B)%9973。

已知n=A%9973，设x=A/B，那么n=A-A/9973*9973=Bx-A/9973*9973，求出x大问题就解决了，最后为了防止负数产生，x=(x%9973+9973)%9973.

#include #include#include#define LL long long#includeusing namespace std;void extend_Euclid(LL a,LL b,LL &f,LL &x,LL &y){if(b == 0) { x = 1; y = 0; f=a; return ;}extend_Euclid(b,a%b,f,x,y);LL tmp = x;x = y;y = tmp - (a / b) * y;}int main(){ //freopen("cin.txt","r",stdin); LL n,B,N; while(cin>>N){ while(N--){ LL a,b,c,f,x,y; scanf("%lld%lld",&n,&B); c=n; b=9973; a=B; extend_Euclid(a,b,f,x,y); x=x*(c/f); cout<<(x%9973+9973)%9973<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。