模线性方程的基本应用
#include<iostream> using namespace std; int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int d=exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return d; } int main() { int b,a,t; scanf("%d",&t); while(t--) { scanf("%d%d",&b,&a); int e,d,x,y,f; d=exgcd(a,9973,x,y); f=9973/d<0?(-1*9973/d):9973/d; e=(x*(b/d)%f+f)%f; printf("%d\n",(e)%9973); } return 0; }
原文:http://www.cnblogs.com/zhangdashuai/p/3699358.html