Atcoder Regular Contest 034_C_約数かつ倍数

水色の問題.そのまま約数列挙するのが不可能なものをどう見るか.

atcoder.jp

問題の説明

個の正整数が与えられる.の約数であり,かつの倍数でもあるものの個数をで割った余りを求めよ.

制約

• 
• 

考えた事

まず階乗のscaleから考えて,どう見ても実際にの約数をすべて列挙しての倍数となっているか判定する方法は間に合わなさそうに見える.¹ ここでは数式から候補を絞ってみよう.そもそもの倍数とはどう書けるか.

とすると,となる.このがの約数となるから,は整数となる.

より,を整数とするためのの候補はの約数と絞られる.

ここまで来たらもう少しだ.の約数の個数をどうやって知ろうか.もちろん素因数分解である.一般に知られている素因数分解の計算量はなので,をひとつの数とまとめてやろうとすると色々苦しい.

ここではの積とみるのがいいだろう.の素因数分解でそれぞれ得た底と指数をまとめるとそれは,の素因数分解を行った結果と同様のものである.² 底と指数をまとめるツールとしてはmapを用いるのがベターだろう.mapのkeyを底として,valueに素因数分解で得られた指数を格納する.

ここまでできたらほぼ終わり.約数の個数を求める場合の重要な性質 「ある数の約数の個数はその数を素因数分解して得られた(指数+1)の総積となる.」を活用するだけである.

これは上で実装したmapを用いて極めて簡単に計算ができる.求めたかったものはの約数かつの倍数であったからこの答えを出力してAC. ここまでお読みいただきありがとうございました.

プログラム

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using mint = modint1000000007;
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
int main() {
    ll A, B;
    cin >> A >> B;
    map<ll, ll> ma;
    reps(x, B + 1, A + 1) {
        ll res = x;
        for (ll i = 2; i * i <= x; i++) {
            ll count = 0;
            while (!(res % i)) {
                res /= i;
                count++;
            }
            if (count) {
                ma[i] += count;
            }
        }
        if (res != 1) {
            ma[res]++;
        }
    }
    mint ans = 1;
    for (auto x : ma) {
        ans *= (x.second + 1);
    }
    cout << ans.val() << endl;
}

---

1. この方式を取るのが5点分のテストケースの問題.↩

2. 結合律に近いニュアンス↩