ACL Contest 1 - Sum is Multiple

問題リンク

解説

式変形すると

となります。とは互いに素であるので、の素因数をとのどちらかに押し付けます

あとは拡大ユークリッド互除法を用いれば、差が1でかつ最小になるようなものを求められます

提出コード

atcoder.jp