P8178 题解

Sky_Maths · 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 的规律：

i	c	d
0	0	0
1	a_1	b_1
2	a_1 \cdot a_2	(b_1) \cdot a_2+b_2
3	a_1 \cdot a_2 \cdot a_3	(b_1 \cdot a_1+b_2) \cdot a_3+b_3
4	a_1 \cdot a_2 \cdot a_3 \cdot a_4	((b_1 \cdot a_1+b_2) \cdot a_3+b_3) \cdot a_4+b_4

眼尖的同学应该已经发现了 c,d 数组的规律：

于是代码变成了这样：

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

P8178 题解

【题意】

【分析】

【简要题意】

【简要题意】

【分析】

【总结】

【代码】