読者です 読者をやめる 読者になる 読者になる

yukicoder ★★ No.415 ぴょん

問題

No.415 ぴょん - yukicoder

考察

とっかかりとしては、NとDが互いに素であれば全て巡ることができそうです。
ここからgcdあたりが関係しそうだなと思いつきます。

一度踏んだ足場をもう一度踏むループに入った時、最初に踏むのは必ず初期位置の足場です。
そのため、↓のような式が作れます。

 N * n = D * m (n,mは正の整数)

 n は円環を何周したかを表し、 m は何回ぴょんしたか(実際は m-1)を表します。
そこで、式変形をしてmを求めます。
mは正の整数、かつ条件を満たす最小のものでないといけません(無い足場は通れないため)ので、 {\frac{N}{D}} は既約である必要があります。
既約分数のN、DをそれぞれN'、D'とすると、↓の式が生まれます。

 m = {\frac{N'}{D'}} * n

 n = D'とすると正の整数かつ条件に合う最小なので、 m = N' となり、 N' - 1が答えです。
既約にするには、gcd(N, D)で割ればよいです。

コード

int main() {
    int N, D;
    cin >> N >> D;

    int g = gcd(N, D);

    cout << N / g - 1 << endl;

    return 0;
}

備考

問題文が一周回ってシュールです。