题解 AT2554 【Choose Integers】

詹詹tv__詹詹 · 2019-09-13 18:04:32 · 题解

不是，我想知道大家看到题都是在想枚举吗。。。

我竟然没有看到我想要的方法。

好吧，事实证明，这道题数据真的是太水了，枚举都能过。

多好的一道最大公约数的题啊！！！

先附上代码（注解版）

#include<bits/stdc++.h>

using namespace std;

int gcd(int x , int y){//最大公约数函数
    while(x % y){//更相减损法进阶：辗转相除法
        int r = x % y;//取余
        x = y;
        y = r;//迭代
    }
    return y;//最大公约数
}

int main(){

    int a , b , c;
    cin >> a >> b >> c;//被除数，除数，余数

    if(c % gcd(a , b) == 0){//这条式子下面会给出证明
        cout << "YES";
    }else{
        cout << "NO";
    }
    return 0;
}

证明：

//证明：
//原题可表示为 
//k * a - p * b = c
//原式 = gcd(a , b) * [k * a / gcd(a , b) - p * b / gcd(a , b)]
//因为 k , p为任意整数
//所以 [k * a / gcd(a , b) - p * b / gcd(a , b)] 可以取任意整数值
//所以当 c 能整除 gcd(a , b)时 , 可以满足题目条件