自动搬运

查看原文

来自洛谷，原作者为

	Sky_Maths **

搬运于2025-08-24 22:36:39，当前版本为作者最后更新于2022-02-26 19:14:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Update：2022/7/21 修改了两个错误

题目传送门：P8178 「EZEC-11」Sequence

【题意】

• 已知数列 $f$ 满足 $f_i=a_i\cdot f_{i-1}+b_i(i\ge1)$ ，

• 问是否存在非负整数 $f_0$ ，使得 $f_i$ 为 质数 $p_i$（ $1\le i \le n$ ）的倍数。

• 本题有多组测试数据，若存在满足条件的 $f_0$ 则输出Yes，否则输出No。

• 对于 $100\%$ 的数据，$1\le T\le10$ ， $1\le n\le10^3$ ， $0\le a_i,b_i\le 10^9$ ， $2\le p_i\le 10^9$ ， $p$ 为质数。

【分析】

• 前置条件：看懂题目，已经会打暴力。
• 最先想到的肯定是枚举 $f_0$ ，若有满足的则输出Yes,否则输出No，但这样的时间复杂度为$O ( \max(f_0,lcm(p_{1,2,\ldots,n}))\cdot n^2 )$。
• 代码类似这样:

	while(f[0]<lcm(all:p[1-n]))
	{
		int flag=0;
		for(int i=1;i<=n;i++)
		{
			f[i]=a[i]*f[i-1]+b[i];
			if(f[i]%p[i])
			{
				flag=1;
				break;
			}
		}
		if(!flag)
		{
			printf("%d",f[0]);
		}
		++f[0];
	}

• 看到 $n^2\le10^6$ 和输出Yes或No想到这是一道数学结论题，考虑去掉 $\max(f_0,lcm(p_{1,2,\ldots,n}))$ 。
• 想到可以将 $f_i$ 用 $c_i \cdot f_0+d_i$ 表示，改变 $f_0$ 后可以用$O(1)$的时间复杂度直接求出 $f_i$ 。
• 先不考虑 $p_i$ ，看一下数组$c$与数组 $d$ 的规律：

• 眼尖的同学应该已经发现了 $c,d$ 数组的规律：
• $c_i=c_{i-1}\cdot a_i$。
• $d_i=d_{i-1}\cdot a_i + b_i$。
• 于是代码变成了这样：

	c[0]=1;
	for(int i=1; i<=n; i++) {
		c[i]=c[i]*a[j];
		d[i]=d[i]*a[j]+b[j];
	}

• 很短吧~
• 但是! $c_i,d_i$ 可能变得很大很大，所以需要当场 $\bmod p_i$。
• $c_i \cdot f_0+d_i\equiv c_i\bmod p_i\cdot f_0+d_i\bmod p_i(\bmod p_i)$
• 考虑 $p_i$，$f_i$ 为 $p_i$ 的倍数,即 $f_i\bmod p_i=0$ ，使 $c_i=c_i \bmod p_i$ ， $d_i=d_i \bmod p_i$。
• 但是， $p_i$ 不一定相同！所以针对每个$p_i$用一个$O( n )$的循环求出 $c_i,d_i$ 。
• 于是用$O( n^2 )$的预处理将这题转变成了另一个问题。

【简要题意】

给出 $n$ 个 $c_i$ , $d_i$ , $p_i$ ,求是否有满足所有公式 $c_i\cdot x+d_i\equiv 0(\bmod p_i)$ 的通项 $x$ 。

• 很容易想到应该将 $x$ 的系数化为1。
• 但是！若 $c_i=0$ ，就无法将 $x$ 的系数化为1，但是！我们可以直接判断是否存在解了！
• 考虑如何判断（这个应该比较简单），直接判断 $d_i\bmod p_i$ 是否等于0，若不等于，则可以判断绝对是不存在解的，若等于则可以不考虑 $i$ ，因为无论 $x$ 等于几都必定有解。
• 那么若 $c_i$ 不等于0，则将 $d_i$ 除上一个 $c_i$ ，但我们已将 $c_i,d_i\bmod p_i$ ，那么考虑求 $p_i$ 的逆元为 $px_i$ ，这里就不做赘述。
• 将 $d_i=d_i\cdot px_i\bmod p_i$
• 于是用$O( n\log n )$的预处理又将这题转变成了另一个问题。

【简要题意】

给出 $n$ 个 $d_i$ , $p_i$ ,求是否有满足所有公式 $(x+d_i)\bmod p_i=0(d_i\ge 0)$ 的通项 $x$。

【分析】

• 公式 $(x+d_i)\bmod p_i=0$ 即 $x+d_i$ 为 $p_i$ 的倍数。
• 所以化为 $x=-d_i=f_i$，
• 令 $f(i)=(i\bmod p_i+p_i)\bmod p_i$ ，
• 使 $f_i=f(d_i)$ ，
• 而保证 $p_i$ 为质数，若 $p_i$ 不同则一定有解，若 $p_i=p_j$ 且 $f_i$ 不等于 $f_j$ ,则必定无解,否则有解。

【总结】

• 以上全部判断完后若还全部满足则可以输出Yes了。

【代码】

#include<cstdio>
#include<unordered_map>
#define N 1009
#define int long long
using namespace std;
unordered_map<int,int>ma;
int t,n,flag;
int a[N],b[N],c[N],d[N],p[N];
int exgcd(int a, int b, int &x, int &y) { 
	if (!b) {
		x=1;y=0;
		return a;
	}
	int q=a/b,r=a%b,ex;
	ex=exgcd(b,r,y,x);
	y-=q*x;
	return ex;
}
main() {
	scanf("%lld",&t);
	while(t--) {
		flag=0;
		scanf("%lld",&n);
		for(int i=1; i<=n; i++)
			scanf("%lld",&a[i]);
		for(int i=1; i<=n; i++)
			scanf("%lld",&b[i]);
		for(int i=1; i<=n; i++)
			scanf("%lld",&p[i]);
		for(int i=1; i<=n; i++) {
			c[i]=1;
			d[i]=0;
			for(int j=1; j<=i; j++) {
				c[i]=c[i]*a[j]%p[i];
				d[i]=(d[i]*a[j]+b[j])%p[i];
			}
/*求c[i]与d[i]，因为p[i]不同，所以针对每个p[i]都1~i枚举一遍
虽然时间复杂度变为了O(n^2)，但没有超时~~~
而且不需要打高精了*/ 
			if(!c[i]&&d[i]) {
				puts("No");
				flag=1;
				break;
			}
			if(!c[i]) {
				p[i]=1e9;
//用一个非质数来代替p[i]防止与真正的p[i]重复
				d[i]=1e9;
				continue;
			}
			int t;
			exgcd(c[i],p[i],c[i],t);
			d[i]=(((-d[i])%p[i]+p[i])%p[i])*c[i]%p[i];
			d[i]=(d[i]+p[i])%p[i];
//将x的系数化为1 
		}
		if(!flag) {
			for(int i=1; i<=n; i++) {
				if(ma[p[i]]&&ma[p[i]]!=d[i]+1) {
					puts("No");
					break;
				} else {
					ma[p[i]]=d[i]+1;
//+1是为了防止d[i]为0误判为没有存过
				}
				if(i==n) {
					puts("Yes");
				}
			}
		}
		ma.clear();
	}
	return 0;
}

• 返回题目：P8178 「EZEC-11」Sequence