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;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/554384.html

標籤：其他

上一篇：必讀：學習C語言編程的路線圖

下一篇：返回列表