CF338D GCD Table 题解
题目描述
你有一个长度为 \(k\) 的数列 \(a\) ，
询问是否存在 \(x\in[1,n]~~~y\in[1,m]\) 使得 \(\forall i~~~ \gcd(x,y+i-1)=a_i\)。
解析
我们转换一下可以得到：
\[\forall i ~~\left\{
\begin{matrix}
x\equiv 0\pmod{a_i} \\
y+i-1\equiv 0\pmod{a_i}
\end{matrix}
\right.
\]
前面一个 \(x\) 很好解决，直接最大公倍数。
\(y\) 可以转化一下：
\[y\equiv 1-i\pmod{a_i}
\]
经典扩展中国剩余定理。
但是我们因为分开考虑的 \(x\) 与 \(y\) 得到的不一定是充要条件。
我们需要再次验证一下。
温馨提示
1.在运算过程中会爆 long long 需要龟速乘。
2.在运算过程中最大公倍数也就是 \(x\) 会爆long long ，我们需要判断一下有没有超过 \(n\) 如果超过直接 NO。
3.计算 \(y\) 的时候有可能 \(y = 0\) 在这个情况下我们考虑 \(y = 0\) 和 \(y = x\) 是等价的我们可以直接赋值成 \(x\) 。文章来源：https://www.toymoban.com/news/detail-472000.html
考虑 \(x\) 还表示了 \(a\) 数列的最大公倍数文章来源地址https://www.toymoban.com/news/detail-472000.html
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4 + 10;
int k;
ll n, m, a[N], x = 1,y = 0,M;
ll mmul(ll x,ll k,ll p){
ll ans = 0,d = x;
while(k){
if(k & 1) ans = (ans + d) % p;
k >>= 1;
d = d * 2 % p;
}
return ans;
}
ll gcd(ll a,ll b){
if(b == 0) return a;
return gcd(b, a % b);
}
void exgcd(ll a,ll b,ll &x,ll &y){
if(b == 0){
x = 1,y = 0;
return ;
}
exgcd(b, a % b, x, y);
ll z = x;
x = y;
y = z - (a / b) * y;
}
ll jfc(ll a,ll b,ll c){
ll x = 0,y = 0,g;
g = gcd(a,b);
a /= g,b /= g;
if(c % g) return -1;
exgcd(a, b, x, y);
return mmul((x % b + b) % b,c / g,b);
}
void input(){
cin>>n>>m>>k;
for(int i = 1; i <= k; ++i){
cin>>a[i];
}
}
bool op(){
for(int i = 1;i <= k; ++i){
ll now = jfc(x,a[i],(((1 - i + a[i]- y) % a[i] + a[i]) % a[i]));
if(now == -1) return 0;
y = (mmul(now,x,x * a[i] / gcd(x,a[i])) + y) % (x * a[i] / gcd(x,a[i]));
x = x * a[i] / gcd(x,a[i]);
if(x > n) return 0;
}
if(y == 0) y = x;
if((y + k - 1) > m) return 0;
return 1;
}
bool pd(){
for(int i = 1;i <= k; ++i){
ll now = gcd(x,y + i * 1ll - 1ll);
if(now != a[i]) return 0 ;
}
return 1;
}
int main(){
input();
if(op() && pd()){
cout<<"YES";
}else{
cout<<"NO";
}
return 0;
}
到了这里，关于CF338D GCD Table 题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
