2017-07-31 cf #426 div2 C. The Meaningless Game 競技プログラミング Codeforces 問題ページ Problem - C - Codeforces 考えたこと 色々数字をいじっていたらそれっぽい解法が思いついて投げたら通った。 gcdを求めたあと素因数分解をしたくなったが、a、bが大きな素数のときに計算時間が怖かったのでこの方針は捨てた。 立法数判定だけなら時間は問題なさそうなのでこの方針で考えると、gcd/{(a/gcd)*(b/gcd)}が立法数か判定したらサンプルや手元で作ったケースを通ったのでこれで投げたら通った。