GCD Products easy [灘校75回生中学卒業記念コンテスト]

https://www.hackerrank.com/contests/75th/challenges/gcd-product-easy

解説

https://www.hackerrank.com/contests/75th/challenges/gcd-product-easy/submissions/code/1321979648

制約を見てみると、iは全探索ができる。
A=1, B=10, N=6が最大であるが、10⁶通りある。
(1,1,1,1,1,1)～(10,10,10,10,10,10)の重複順列を全列挙する方法だが、
重複順列を全列挙するにはDFSを使うといい。
あとは、gcdを計算して総積をとると答え。

int A, B, N;
//---------------------------------------------------------------------------------------------------
mint ans = 1;
void dfs(int cu, int g) {
    if (cu == N) {
        ans *= g;
        return;
    }
    
    rep(i, A, B + 1) dfs(cu + 1, gcd(g, i));
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> N;
    dfs(0, 0);
    cout << ans << endl;
}