/*
这是一个简单的用“扩展欧几里得”求解乘法逆元的程序,洛谷P3811: https://www.luogu.com.cn/problem/P3811
样例输入 10,13
样例输出 1,7,9,10,8,11,2 ,5, 3,4
最诡异的是,在函数exgcd()中第一行的cout语句如果执行的话,答案就是正确的,如果不执行,答案就是错误的。
???? 求指教
*/
#include <iostream>
using namespace std;
void exgcd(int a,int b,int gcd, int&x, int&y); //已经gcd(a,b), 求gcd(a,b)的线性组合 ax+by ; 其中 a>b
int main(){
int n,p;
cin>>n>>p;
int x,y;
for(int i=1;i<=n;i++){
exgcd(i,p,1,x,y);
cout<<(y%p+p)%p<<endl;
}
return 0;
}
void exgcd(int a,int b,int gcd, int&x, int&y){
//cout<<endl<<"a="<<a<<",b="<<b<<endl; //【这一句如果执行的话,答案就是正确的。】
if(a<b)
swap(a,b);
if(0==b){
x=gcd/a;
return;
}
int xt,yt;
//递归
exgcd(b,a%b,gcd,xt,yt); //用引用类型返回xt,yt
x=yt;
y=xt-a/b*yt;
return;
}