B3831题解

xiongzecheng · 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;
}