CF338D GCD Table 题解
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\) 。
考虑 \(x\) 还表示了 \(a\) 数列的最大公倍数
代码
#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;
}
热门相关:骑士归来 重生之至尊千金 惊世毒妃:轻狂大小姐 朕 夫人你马甲又掉了