TechFUL: Techちゃんとバウムクーヘン泥棒【easy】

問題概要

Techちゃんは好みの男の子にバウムクーヘンを作りたい．

Techちゃんは 個入りのバウムクーヘンを好きな個数だけ自由に作る．

しかし、バウムクーヘンの個数が 個以上のとき、 個未満になるまでカラスの集団が 個ずつ食べてしまう．

男の子は 個のバウムクーヘンを貰うと Tech ちゃんを好きになる．

男の子が Tech ちゃんを好きにさせることが可能か判定せよ．

問題のリンク

制約

• 
• 

解法

Tech ちゃんが 個のバウムクーヘンを作り、

カラスが 個バウムクーヘンを食べたとする．

このとき、 が成り立つ．

これを式変形すると、 という一次不定方程式になる．

この方程式が整数解を持つための必要十分条件は r が gcd(x, m) の倍数を満たすことである．

一次不定方程式については以下の drken さんの記事が参考になる．

qiita.com

この方程式の整数解がどちらも 0 以上になるかを考える．

を を満たす整数解の一つとする．

また、 を となる整数とすると、 より は同符号である．

となるため、 も一次不定方程式の整数解となる．

を十分大きな値にすれば、 はどちらも 以上の整数にすることができる．

よって、 には 以上の整数解 が存在する．

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long x, m, r;
    cin >> x >> m >> r;
    cout << (r % gcd(x, m) == 0 ? "Yes" : "No") << endl;
}