扩展中国剩余定理求调
查看原帖
扩展中国剩余定理求调
164580
YGB_XU楼主2022/5/29 18:11

rt,第一个点一直 WA,别的点都能过。有做过这道题的大佬说一下本题坑点也行…

#include<bits/stdc++.h>
using namespace std;

inline int read(){
	int ret=0,f=1;
	char c=getchar();
	while(c<'0'||'9'<c){
		if(c=='-') f=-1;
		c=getchar();
	}
	while('0'<=c&&c<='9'){
		ret=(ret<<1)+(ret<<3)+(int)(c-'0');
		c=getchar();
	}
	return ret*f;
}

inline long long readll(){
	long long ret=0ll,f=1ll;
	char c=getchar();
	while(c<'0'||'9'<c){
		if(c=='-') f=-1ll;
		c=getchar();
	}
	while('0'<=c&&c<='9'){
		ret=(ret<<1ll)+(ret<<3ll)+(long long)(c-'0');
		c=getchar();
	}
	return ret*f;
}

inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>=10) write(x/10);
	putchar('0'+x%10);
}

inline void writell(long long x){
	if(x<0ll){
		putchar('-');
		x=-x;
	}
	if(x>=10ll) writell(x/10ll);
	putchar('0'+x%10ll);
}

typedef long long LL;

#define int long long

const int NR=25;
int a[NR],n[NR];

int d,x,y;
inline void exgcd(int a,int b){
	if(b==0){
		d=a;
		x=1;
		y=0;
		return;
	}
	exgcd(b,a%b);
	int t=x;
	x=y;
	y=t-(a/b)*y;
}

inline int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}

inline int lcm(int a,int b){
	return a/gcd(a,b)*b;
}

inline int qmul(int x,int k,int MOD){
	if(k==0) return 0;
	int tmp=qmul(x,k>>1ll,MOD);
	tmp=(tmp+tmp)%MOD;
	if(k&1ll) tmp=(tmp+x)%MOD;
	return tmp;
}

inline void excrt(int N){
	int _lcm;
	for(int i=2;i<=N;i++){
		if(a[i]<a[i-1]){
			swap(a[i],a[i-1]);
			swap(n[i],n[i-1]);
		}
		exgcd(n[i-1],n[i]);
		if((a[i]-a[i-1])%d!=0){
			puts("NIE");
			return;
		}
		x=qmul(x,(a[i]-a[i-1])/d,(n[i]/d));
		x=(x%(n[i]/d)+(n[i]/d))%(n[i]/d);
		// if(x==0) x=(n[i]/d);
		_lcm=lcm(n[i-1],n[i]);
		a[i]=(a[i-1]+qmul(x,n[i-1],_lcm))%_lcm;
		n[i]=_lcm;
	}
	cout<<(a[N]==0?n[N]:a[N])<<'\n';
}

bool vis[NR];
signed main(){
//	ios::sync_with_stdio(false);
	int N=read();
	for(int i=1,now=1,ix,cnt=0;i<=N;i++){
		ix=read();
		if(vis[ix]==true){
			puts("NIE");
			return 0;
		}
		vis[ix]=true;
		cnt=0;
		while(now!=ix){
			if(vis[now]==false) cnt++;
			now=(now%N)+1;
		}
		now=(ix%N)+1;
		a[i]=(cnt+1)%(N-i+1);
		n[i]=N-i+1;
	}
	excrt(N);
	return 0;
}
/*
1 2 3 4 (1 -> %4=1)
2 3 4 (4 -> %3=0)
2 3 (3 -> %2=0)
2 (2 -> %1=0)

x=p*n[i-1]+a[i-1]=q*n[i]+a[i]
p*n[i-1]-q*n[i]=a[i]-a[i-1]
*/
2022/5/29 18:11
加载中...