tj

Igallta · 2023-06-11 16:58:34 · 题解

只需要运用裴蜀定理即可。

裴蜀定理是：当 a , b 为整数，那么对于任意整数 x，y，ax+by 一定是 \gcd(a,b) 的倍数。

现在，我们的式子是 ax+by=c，所以就判断一下 c 是不是 \gcd(a, b) 的倍数就可以了。

又有人要问了，你这说的是“那么对于任意整数 x，y，ax+by 一定是 \gcd(a, b) 的倍数”，可你这个是它的倍数啊！

我们只需要把 x，y 乘上一个数就可以了。所以可以找到。

代码：

#include<bits/stdc++.h>
using namespace std;
int t,a,b,c;
int main(){
    cin>>t;
    for(int i=1;i<=t;i++){//用for可以更简便。 
        cin>>a>>b>>c;
        if(!(c%__gcd(a,b))){
            printf("Case %d:Yes\n",i);//裴蜀定理 
        }       
        else printf("Case %d:No\n",i);
    }
    return 0;
}