AtCoder Regular Contest 046 D - うさぎとマス目

問題

arc046.contest.atcoder.jp

解法

完全に解説がわかりやすいのでそちらを見ましょう。

AtCoder Regular Contest 046 from AtCoder Inc.

www.slideshare.net

const ll MOD = 1e9+7;
ll fact[1000100];
ll rfact[1000100];

// extgcd
ll extgcd(ll a, ll b, ll& x, ll& y) {
    ll d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}

// mod_inverse
ll mod_inverse(ll a, ll m) {
    ll x, y;
    extgcd(a, m, x, y);
    return (m+x%m) % m;
}

ll nCr(int n, int r) {
    ll ret = fact[n]*rfact[n-r]%MOD;
    ret = ret*rfact[r]%MOD;
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    fact[0] = rfact[0] = 1;
    for (int i = 1; i < 1000100; i++) {
        fact[i] = (fact[i-1]*i)%MOD;
        rfact[i] = mod_inverse(fact[i], MOD);
    }
    ll H, W;
    cin >> H >> W;
    ll G = __gcd(H, W);
    ll ans = 0;
    for (ll x = 1; x < G; x++) {
        ll y = G-x;
        ll cx = W/__gcd(W, x);
        ll cy = H/__gcd(H, y);
        if (cx/__gcd(cx, cy)*cy*G == H*W) {
            (ans += nCr(G, x)) %= MOD;
        }
    }
    cout << ans << endl;
    return 0;
}