?? 解模線性方程ax=b(mod n).cpp
字號:
#include<stdio.h>
int ext_euclid(int a,int b,int &x,int &y)
{
int t,d;
if (b==0){
x=1;
y=0;
return a;
}
d=ext_euclid(b,a%b,x,y);
t=x;
x=y;
y=t-a/b*y;
return d;
}
/********************************************
求解模線性方程 ax=b (mod n) ,n>0
*********************************************/
void modular_linear_equation_solver(int a,int b,int n)
{
int e,i,d;
int x,y;
d = ext_euclid(a,n,x,y);
if(b%d>0) printf("No answer!\n");
else
{
e=(x*(b/d))%n;
for (i=0;i<d;i++) //notice! here x maybe <0
printf("The %dth answer is:%ld\n",i+1,(e+i*(n/d))%n);
}
}
int main()
{
int a,b,n;
while(scanf("%d %d %d",&a,&b,&n) != EOF)
modular_linear_equation_solver(a,b,n);
return 0;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -