题解：CF1155C Alarm Clocks Everywhere

题目分析

第二行输入了每次闹钟响的时间，第三行输入了间隔时间。而

x_i

和

p_i

都非常大，所以无法暴力。后来转念一想，任意一个

p_i

如果是他们的最大公因数，就输出 Yes，否则就输出 NO，这道题的核心就是求最大公因数。

题目解法

其实分析完题目，就大致知道怎么写了。本题就是求这些时间间隔之差的最大公因数。最后再循环枚举

p_i

能否被他们的最大公因数整除，能就输出 YES，然后输出

x_1

和当前的

p_i

就可以结束了，否则输出 NO。

AC 代码

CPP

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

题解：CF1155C Alarm Clocks Everywhere

文章操作

题目分析

题目解法

AC 代码

相关推荐

评论

题解：CF1155C Alarm Clocks Everywhere