SP21357 CEQU - Crucial Equation tj

_colin1112_ · 2023-06-12 17:17:00 · 题解

运用知识

以下资料取自百度百科。

裴蜀定理（或贝祖定理）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数 a,b 和它们的最大公约数 d，关于未知数 x 和 y 的线性不定方程（称为裴蜀等式）：若 a,b 是整数,且 \gcd(a,b)=d，那么对于任意的整数 x,y,ax+by 都一定是 d 的倍数，特别地，一定存在整数 x,y，使 ax+by=d 成立。它的一个重要推论是：a,b 互质的充分必要条件是存在整数 x,y 使 ax+by=1。

题目思路

运用裴蜀定理进行模拟即可。可以时输出 Yes，反之则输出 No。

Tips：由于要将字符串及变量同时输出，所以这里选用 printf 来输出。

AC Code

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'

using namespace std;
const int E=1e6+5;
ll n,a,b,c;
int main(){
    cin >>n;
    for(int i=0;i<n;i++){
        cin >>a>>b>>c;
        if((c%__gcd(a,b))==0){
            printf("Case %d: Yes\n",i+1);
            continue;
        }
        printf("Case %d: No\n",i+1);
    }
    en:
    return 0;
}