exgcd可过
查看原帖
exgcd可过
490993
zty02281128楼主2024/11/11 19:16

加上快读486ms

#include<bits/stdc++.h>
using namespace std;
static char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define pc(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
inline int read(){
    int x=0;int f=1;char c=gc();
    for(;c<'0'||c>'9';c=gc())if(c=='-')f=-1;
    for(;c>='0'&&c<='9';c=gc())x=(x<<1)+(x<<3)+c-'0';
    return x*f;
}
static char cc[20];
inline void print(int x,char c){ 
    if(!x)pc('0');
    int len=0;
    if(x<0)x=-x,pc('-');
    while(x)cc[len++]=x%10|'0',x/=10;
    while(len--)pc(cc[len]);pc(c);
}
#define ll int
ll mod,n;
void exgcd(ll a,ll b,ll &x,ll &y){
	if(!b) return x=1,y=0,void();
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
inline int gt(int x){
	while(x<0)x+=mod;
	return x;
}
int main(){
	ll x,y;
	n=read(),mod=read();
	for(int i=1;i<=n;i++){
		exgcd(i,mod,x,y);
		print(gt(x),'\n');
	}
	fwrite(obuf,p3-obuf,1,stdout);
	return 0;
}
2024/11/11 19:16
加载中...