【题解】CF687B Remainders Game

· · 题解

题目传送

博客食用（如果需要的话）

题目简述

给出一个数字 k，以及 n 个数字 \{c_1,c_2,...,c_n\}，

询问是否对于任意的正整数 x，都能根据 x\ \bmod\ c_i(i=1,2,...,n) 的值，求出唯一的 x\ \bmod\ k。

本篇题解的不同之处？

针对一些结论给出了简单的证明。

前置知识（不会也没关系，反正会有简单证明）

我们先将题目换一个形式：

已知 \left\{\begin{matrix}x\ \bmod\ c_1=b_1\\x\ \bmod\ c_2=b_2\\...\ ...\\x\ \bmod\ c_n=b_n\end{matrix}\right.，

询问在 \bmod\ k 的情况下 x 是否有唯一解。

看到这个形式，我们可以很容易地想到中国剩余定理（CRT），

再观察题面可以发现 \{c_1,c_2,...,c_n\} 其实并不两两互质，所以这并不是中国剩余定理（或者说并不完全是），而是扩展中国剩余定理（exCRT）。

在脑子中进行了一个查的询，发现脑子中没有留下任何中国剩余定理的相关内容（我太菜了 QAQ），于是匆匆翻找笔记 ing

找到了残存的笔记：

\left\{\begin{matrix}x\ \bmod\ c_1=b_1\\x\ \bmod\ c_2=b_2\end{matrix}\right.\to x\equiv \colorbox{black}{\color{black}数据删除}(\bmod\ \text{lcm}(c_1,c_2))

好，虽然只找到了一点，但对于解决这道题来说够用了。

题目分析（已经充分掌握前置知识的话可跳过前半部分）

首先，观察题面，发现在不考虑 \bmod\ k 的情况下一定是存在解的

（因为是先有的 x，才有的 \{b_1,b_2,...,b_n\}）。

假设已经有了一个解 x' 满足上述方程，那么 x' 一定可以写成 x'=c_1+k_1b_1=c_2+k_2b_2(k_1,k_2\in Z) 的形式，

于是 x''=x'+k_3\text{lcm}(c_1,c_2)(k_3\in Z) 也一定是一个解，

因此满足以上同余方程的解有无穷多个，并且两两之间至少相差 \text{lcm}(c_1,c_2)，

于是上述同余方程在 \bmod\ \text{lcm}(c_1,c_2) 下至少有一个解。

那么是否有唯一解呢？有如下证明：

假设存在 0\le x,y<\text{lcm}(c_1,c_2)，满足：

\left\{\begin{matrix}x\ \bmod\ c_1=b_1\\x\ \bmod\ c_2=b_2\end{matrix}\right.$，$\left\{\begin{matrix}y\ \bmod\ c_1=b_1\\y\ \bmod\ c_2=b_2\end{matrix}\right.

那么可得：

\left\{\begin{matrix}(x-y)\ \bmod\ c_1=0\\(x-y)\ \bmod\ c_2=0\end{matrix}\right.

因此，\text{lcm}(c_1,c_2)|(x-y)，

但 0\le x,y<\text{lcm}(c_1,c_2)，

于是只存在一种情况：x=y\to(x-y)=0。

所以上述同余方程在 \bmod\ \text{lcm}(c_1,c_2) 的情况下有且仅有一个解。

以上也就是对 \left\{\begin{matrix}x\ \bmod\ c_1=b_1\\x\ \bmod\ c_2=b_2\end{matrix}\right.\to x\equiv \colorbox{black}{\color{black}数据删除}(\bmod\ \text{lcm}(c_1,c_2)) 的具体解释。

同理可证，在其它长度为 \text{lcm}(c_1,c_2) 也仅存在唯一解，

所以我们刚刚写的 x''=x'+k_3\text{lcm}(c_1,c_2)(k_3\in Z) 其实包含了所有解，

我们可以发现，对于这些解来说只要 k|\text{lcm}(c_1,c_2)，那么在 \bmod\ k 的情况下的结果是唯一的，即 x'\ \bmod\ k。

对于 \left\{\begin{matrix}x\ \bmod\ c_1=b_1\\x\ \bmod\ c_2=b_2\\...\ ...\\x\ \bmod\ c_n=b_n\end{matrix}\right. 来说，与 \left\{\begin{matrix}x\ \bmod\ c_1=b_1\\x\ \bmod\ c_2=b_2\end{matrix}\right. 同理。

因此我们只需要判断 k 是否满足 k|\text{lcm}\{c_1,c_2,...,c_n\} 即可。

值得注意的是，直接计算 \text{lcm}\{c_1,c_2,...,c_n\} 的话在 long long 中也会溢出，

对此有两种解决方式：

  1. 将 k 和 \text{lcm}\{c_1,c_2,...,c_n\} 质因数分解，对每个 p_k^a 判定是否存在 p_c^b 使得 p_k^a|p_c^b。

  2. 提前取模，防止溢出（好事多模嘛）

本题解采用的是第二种。

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline void read(int &n){
    n=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')n=(n<<1)+(n<<3)+(ch^48),ch=getchar();
    n*=f;
}
//快读(int)
inline void read_(ll &n){
    n=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')n=(n<<1)+(n<<3)+(ch^48),ch=getchar();
    n*=f;
}
//快读(long long) 
inline void print(int n){
    if(n<0)putchar('-'),n=-n;
    if(n>9)print(n/10);
    putchar(n%10+'0');
}
//快写(int)
inline void print_(ll n){
    if(n<0)putchar('-'),n=-n;
    if(n>9)print_(n/10);
    putchar(n%10+'0');
}
//快写(long long) 
inline void check1(){puts("完成啦！");}
inline void check2(){puts("竟然已经运行到这里了吗？");}
inline void check3(){puts("我已经完全爱上 Warma 啦！");}
//调试程序 
int n,k,c;ll lcm=1;
inline int gcd(int a,int b){return !b?a:gcd(b,a%b);}
//求 gcd
int main(){
    read(n),read(k);
//  读入 
    for(int i=1;i<=n;i++)read(c),(lcm=lcm/gcd(lcm,c)*c)%=k;
//  读入+lcm 计算(注意先除后乘)+取模 
    if(lcm%k)puts("No");else puts("Yes");
//  取模+判断 
    return 0;
}

提交记录