自动搬运

查看原文

来自洛谷，原作者为

	xiongzecheng xiongzecheng！今天要开心呦！不求完成代码，只求在c++上获得快乐！

搬运于2025-08-24 21:15:20，当前版本为作者最后更新于2023-09-02 18:05:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析：

我们可以把题目分拆成如下两个问题：

问题一：给定整数 $t$，它是“$k$-不变”的，求 $k$ 的最小值。

我们可以模拟整数 $t$ 每次替换后的数，并记录替换的次数，等到变成它自己后给出答案。

注意：有些数经过无穷次替换后也无法变回它自己。显然，如果一个数替换的次数超过 $p$ 次后仍未变回它自己，那么这个数就永远无法变回它自己。这样，我们将答案记为 INT_MAX 即可。

显然，以下命题成立：

• 大于等于 $p$ 的数一定经过无穷次变换后也无法变回它自己。

• 如果一个数是“$k$-不变”的，那么它一定是“$A \times k$-不变”的。其中 $A$ 是正整数。

问题二：如何得出题目中的答案？

可以先令 $t=0,1,2,\dots,p-1$，用数组存储下答案，随后遍历输入的数组，找出小于 $p$ 且答案是 $k$ 的因数的数的个数。最后输出即可。

#include<bits/stdc++.h>
using namespace std;
int n,x,y,p,a[1005],l[100005];
int huan(int a,int chu,int cnt){
	if(a==chu&&cnt!=0)return cnt;
	if(cnt>p)return INT_MAX;
	return huan((x*a+y)%p,chu,cnt+1);
}//求出问题一所描述的答案。 
int main(){
	scanf("%d%d%d%d",&n,&x,&y,&p);
	x%=p,y%=p;
	//显然，将x,y,对p取模后结果不变，此处是为了防止爆int。 
	for(int i=0;i<p;i++)a[i]=huan(i,i,0);//将0,1,2,...,p的答案记录下来。 
	for(int i=1;i<=n;i++){
		scanf("%d",&l[i]); 
	}
	int q;scanf("%d",&q);
	while(q--){
		int cnt=0;
		int k;scanf("%d",&k);
		for(int i=1;i<=n;i++)
			if(l[i]<p&&k%a[l[i]]==0)cnt++;
		//遍历数组，求出答案。 
		printf("%d\n",cnt);
	}
	return 0;
}