题解 AT2554 【Choose Integers】

Juvenile · 2019-06-08 11:13:05 · 题解

注意：神犇勿入

这是一份神奇的题解

回归正题

以一道数学题的角度来解释一下：

可以看出若 l=gcd(a,b) 则必有 c≡0(mod l

神奇的证明：

设 l=gcd(a,b)

a=x × l,b=y × l (x,y为正整数)

则必有 a × i=b × k+c (i,k为正整数)

x × l × i = y × l × k +c

可得 l × (x × i - y × k)=c

因为x,y,k均为正整数,所以c为l的倍数

否则无法得到c

给出华丽的代码：

#include <bits/stdc++.h>
using namespace std;
int a,b,c;
int gcd(int a,int b)
{
    while(b^=a^=b^=a%=b);//玄学
    return a;
}
int main()
{
    scanf("%d%d%d",&a,&b,&c);
    int l=gcd(a,b);
    if(c%l!=0) printf("NO");
    else printf("YES");
}