专栏首页饶文津的专栏「AtCoder Grand018A」Getting Difference(GCD)

「AtCoder Grand018A」Getting Difference(GCD)

题目链接A - Getting Difference

题意

有n(1~\(10^5\))个数\(A_i\) (110^9),每次选两个数,将它们的差的绝对值加入这堆数。问k(1\(10^9\))是否可能出现在这堆数中。

题解

因为选择的数的差一定是这两个数的gcd的倍数,因此可以令g为所有数的gcd,那么g的不超过数组中最大值的倍数都是可以得到的。

代码

#include <cstdio>
#define N 100005
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
int n,k;
bool ans;
int a[N];
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]),ans|=a[i]>=k;
	int g=a[1];
	for(int i=2;i<=n;++i)
		g=gcd(a[i],g);
	ans&=(k%g==0);
	puts(ans?"POSSIBLE":"IMPOSSIBLE");
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BUPT2017 wintertraining(15) #2 题解

    ​ 因为2520%pre_lcm0,所以x%pre_lcm(x%2520)%pre_lcm

    饶文津
  • 【校赛小分队之我们有个女生】训练赛1

    校赛小分队之我们有个女生队——这是我、ljh学长、zk大神组的队,我取得闪亮亮的队名!

    饶文津
  • 快速傅里叶变换FFT& 数论变换NTT

    0(000)2(010)4(100)6(110),1(001)3(011)5(101)7(111)

    饶文津
  • Codeforces Round #547 (Div. 3) C. Polycarp Restores Permutation(思维)

    题目链接:https://codeforces.com/contest/1141/problem/C

    Ch_Zaqdt
  • BZOJ4241: 历史研究(回滚莫队)

    如果询问的两个端点在同一个块中,直接暴力计算,时间复杂度$O(\sqrt{n})$

    attack
  • 2491 玉蟾宫

    2491 玉蟾宫 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 大师 Master 题目描述 Description   有一天...

    attack
  • 车站分级 拓扑排序

    用户2965768
  • 51nod 1597 有限背包计数问题 (背包 分块)

    对于前\(m\)个直接暴力,利用单调队列优化多重背包的思想,按\(\% i\)分组一下。复杂度\(O(n\sqrt{n})\)

    attack
  • 2017icpc beijing-I题-Colored Nodes

    题意:给出n个点m条边 然后每个时间点,与这个位置相连的所有点就会变成这个点的颜色 比如时间1的时候就是以这个位置相连的点2 变成1的颜色同理如下,通过2个循环...

    逐梦的青春
  • 2017.7.21夏令营清北学堂解题报告

    预计分数: 60+30+0=90=划水 实际分数: 90+30+20=140=rank5=雷蛇鼠标 一句话总结:今天该买彩票! T1: 题目描述 从前有一个?...

    attack

扫码关注云+社区

领取腾讯云代金券