嘘解法かも
なんとなくで出したら通ってしまった。
多分正式な解答ではない（加えて嘘解法かもしれない）ので、ただの読み物としてよむことをオススメする。
数学的な問題っぽい。
とりあえずググるか「二元一次方程式 整数解」とやると、いつものサイトが出てくる。
これによると、Xがgcd(A,B)の倍数であれば、整数解になるっぽい。
とりあえず、これは判定しておき、そうじゃないならNo
あとは、整数解の中に自然数ペアがあるかどうか。
適当に出てきたこれのhir******さんのやつを参考に一般解を考える。
g = gcd(A,B)して、A,B,Xをgで割ったものを以降は考える。
Ax+By=X
By=X-Ax
By=A(X/A-x)
A,Bは互いに素なので、
X/A-x=Bk より x=X/A-Bk
y=Ak
となる。yは整数となる必要があるので、k=s/Aと考えて変形しよう。
x=X/A-Bs/A
y=s
で、x,yは0以上なので、
0≦X/A-Bs/A より Bs/A≦X/A より s≦X/B
0≦s
これでsの範囲が分かる。
ここからが分からなかったので、上限を設けてsを全探索したら通った。
int A, B, X; //--------------------------------------------------------------------------------------------------- #define yes "Yes" #define no "No" string solve() { int g = gcd(A, B); if (X % g != 0) return no; A /= g; B /= g; X /= g; rep(s, 0, max(1010101, X / B + 10)) { int y = s; ll x = X - 1LL * B * y; if (x % A == 0 and 0 < x / A) return yes; } return no; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> A >> B >> X; cout << solve() << endl; }
