首页 > 其他 > 详细

test20200425 迫害 DJ

时间:2020-04-25 18:53:13      阅读:113      评论:0      收藏:0      [点我收藏+]

迫害 DJ

舰队 collection 2019 年秋季活动 E1,第八驱逐队正在讨论要怎么迫害 DJ.

大潮表示,她左手的内火艇能对 DJ 造成 \(g_0 = a\) 点伤害,右手的战车能对 DJ 造成 \(g_1 = b\) 点伤害。

满潮表示,司令部研发的若干新式对陆武器,第 \(i\) 件可以对 DJ 造成 \(g_i = 3 ? g_{i?1} ? g_{i?2}\) 点伤害。

荒潮表示,司令部已经发现了 DJ 的弱点,可以对 DJ 造成巨大倍率的伤害,具体公式为:

\[f_{n,0} = n , f_{n,k} = f_{g_n,k?1} \]

朝潮现在已经知道了 \(a, b, n, k\) 的值,汇报给了提督你,现在请你算出可以对 DJ 造成多大的伤害。

请你把 \(f_{n,k}\)\(p\) 取模的结果告诉在前线的第八驱逐队。

\(0\le a,b < p, 1\le T\le 1000, 1\le n,p\le 10^9,1\le k\le 100\)

找规律

其实就是斐波那契数列嵌套\(k\)次。显然我们需要找斐波那契数列模\(p\)的循环节。

斐波那契数列循环节是经典找规律问题,用BSGS打表:

signed main(){
	freopen("table.out","w",stdout);
	int n=1e5;
	for(int P=1;P<=n;++P){
		if(P%10000==0) cerr<<P<<endl;
		function<matrix(CO matrix&,CO matrix&)> mul=[&](CO matrix&a,CO matrix&b)->matrix{
			matrix ans={};
			for(int k=0;k<2;++k)
				for(int i=0;i<2;++i)for(int j=0;j<2;++j)
					ans[i][j]=(ans[i][j]+a[i][k]*b[k][j])%P;
			return ans;
		};
		function<matrix(matrix,int)> pow=[&](matrix a,int b)->matrix{
			matrix ans={1,0,0,1};
			for(;b;b>>=1,a=mul(a,a))
				if(b&1) ans=mul(ans,a);
			return ans;
		};
		int S=ceil(sqrt(10*P));
		matrix a={3,P-1,1,0},b={1,0,0,1};
		map<matrix,int> H={{b,0}};
		for(int i=1;i<S;++i) H[b=mul(a,b)]=i;
		a=mul(a,b),b={1,0,0,1};
		int ans=-1;
		for(int i=1;i<=S;++i)
			if(H.count(b=mul(a,b))) {ans=i*S-H[b]; break;}
		printf("%lld %lld\n",P,ans);
//		int u=1%P,v=1%P;
//		cerr<<" "<<v;
//		for(int i=1;i<=ans+1;++i){
//			cerr<<" "<<u;
//			int t=u;u=(3*u+P-v)%P,v=t;
//		}
//		cerr<<endl;
	}
	return 0;
}
1 1
2 3
3 4
4 3
5 10
6 12
7 8
8 6
9 12
10 30
11 5
12 12
13 14
14 24
15 20
16 12
17 18
18 12
19 9
20 30
21 8
22 15
23 24
24 12
25 50
26 42
27 36
28 24
29 7
30 60

注意到我们不需要求最短循环节,所以可以对最短循环节进行放大,使得它与模数比较接近。

先看质数的情况:

  • \(5\rightarrow 10\),比较特殊。

  • \(+1:2,3,7,13,17,23\),它们\(\equiv 2,3\pmod 5\)

  • \(-1:11,19,29\),它们\(\equiv 1,4\pmod 5\)

记质数的变化为\(F(x)\),然后看合数的情况。容易得到

\[x=\prod_{i=1}^{\omega}p_i^{\alpha_i}\rightarrow \operatorname{lcm}_{i=1}^{\omega}(F(p_i)p_i^{\alpha_i-1}) \]

卡常数

注意到我们要做\(10^5\)次质因数分解。能够不写Pollard-Rho吗?

事实上,这个循环节是有不动点的,比如\(60\rightarrow 60\)

那么用unorderd_map记录循环节的结果就行了。

int mod;
matrix operator*(CO matrix&a,CO matrix&b){
	matrix ans={};
	for(int k=0;k<2;++k)
		for(int i=0;i<2;++i)for(int j=0;j<2;++j)
			ans[i][j]=(ans[i][j]+a[i][k]*b[k][j])%mod;
	return ans;
}
matrix pow(matrix a,int b){
	matrix ans={1,0,0,1};
	for(;b;b>>=1,a=a*a)
		if(b&1) ans=ans*a;
	return ans;
}

int pri[100000],tot;
unordered_map<int,int> H; // edit 1

int calc(int P){
	if(H.count(P)) return H[P];
	int&ans=H[P]=1;
	for(int i=1;i<=tot and pri[i]*pri[i]<=P;++i)if(P%pri[i]==0){
		int sum=pri[i]==5?10:(pri[i]%5==2 or pri[i]%5==3?pri[i]+1:pri[i]-1);
		for(P/=pri[i];P%pri[i]==0;P/=pri[i]) sum*=pri[i];
		ans=lcm(ans,sum);
	}
	if(P>1){
		int sum=P==5?10:(P%5==2 or P%5==3?P+1:P-1);
		ans=lcm(ans,sum);
	}
	return ans;
}

int P[101];

void real_main(){
	int a=read<int>(),b=read<int>();
	int n=read<int>(),K=read<int>();
	read(P[1]);
	for(int i=2;i<=K;++i) P[i]=calc(P[i-1]);
	for(int i=K;i>=1;--i){
		mod=P[i];
		if(n==0) {n=a; continue;}
		n=(pow((matrix){3,mod-1,1,0},n-1)*(matrix){b,0,a,0})[0][0];
	}
	printf("%lld\n",n);
}
signed main(){
	int n=ceil(sqrt(1e9));
	for(int i=2;i<=n;++i){
		if(!pri[i]) pri[++tot]=i;
		for(int j=1;j<=tot and i*pri[j]<=n;++j){
			pri[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
	for(int T=read<int>();T--;) real_main();
	return 0;
}

test20200425 迫害 DJ

原文:https://www.cnblogs.com/autoint/p/12774436.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!