题解：CF1155C Alarm Clocks Everywhere

· · 题解

题目分析

第二行输入了每次闹钟响的时间，第三行输入了间隔时间。而 x_i 和 p_i 都非常大，所以无法暴力。后来转念一想，任意一个 p_i 如果是他们的最大公因数，就输出 Yes，否则就输出 NO，这道题的核心就是求最大公因数。

题目解法

其实分析完题目，就大致知道怎么写了。本题就是求这些时间间隔之差的最大公因数。最后再循环枚举 p_i 能否被他们的最大公因数整除，能就输出 YES，然后输出 x_1 和当前的 p_i 就可以结束了，否则输出 NO。

AC 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,m;
    cin>>n>>m;
    int a;
    cin>>a;
    int gcd=0;
    for(int i=1;i<n;i++){
        int x;
        cin>>x;
        if(x-a==0)gcd=a;
        else gcd=__gcd(gcd,abs(x-a));
    }
    for(int i=1;i<=m;i++){
        int p;
        cin>>p;
        if(gcd%p==0){
            cout<<"YES\n"<<a<<" "<<i;
            return 0;
        }
    }
    cout<<"NO";
}