ferinの競プロ帳

競プロについてのメモ

cf #426 div2 C. The Meaningless Game

問題ページ
Problem - C - Codeforces

考えたこと

色々数字をいじっていたらそれっぽい解法が思いついて投げたら通った。
gcdを求めたあと素因数分解をしたくなったが、a、bが大きな素数のときに計算時間が怖かったのでこの方針は捨てた。
立法数判定だけなら時間は問題なさそうなのでこの方針で考えると、gcd/{(a/gcd)*(b/gcd)}が立法数か判定したらサンプルや手元で作ったケースを通ったのでこれで投げたら通った。