競プロ日記#25/05/20

アルゴ式

Ex. エラトステネスの区間篩

• 素数判定の関数をそのまま使ってもBの入力制約が1e12なのでTLEしそう
• シンプルに考えるなら√B以下で探せばいいかなと思ったが問題文にヒントっぽく配置されている「A,B はとても大きな整数となる可能性がありますが、B−A は小さな整数であることに注意しましょう。」の利用の仕方が良くわからなかった
  →√B以下で探せばよいらしかった...

int main() {
    // 入力が 32 ビット整数型に収まらないので long long 型
    long long A, B;
    cin >> A >> B;

    // √B 以下の素数を炙り出すための篩
    // ここでは大きめにサイズ 1100000 まで確保しておく
    vector<bool> isprime(1100000, true);

    // A 以上 B 以下の整数 v が素数かどうか
    // その答えは isprime2[v-A] に格納される
    vector<bool> isprime2(B - A + 1, true);

    // ふるい
    for (long long p = 2; p * p <= B; ++p) {
        // すでに合成数であるものはスキップする
        if (!isprime[p]) continue;

        // p 以外の p の倍数から素数ラベルを剥奪
        for (long long q = p * 2; q * q <= B; q += p) {
            isprime[q] = false;
        }

        // start: A 以上の最小の p の倍数
        long long start = (A + p - 1) / p * p;
        if (start == p) start = p * 2;

        // A 以上 B 以下の整数のうち、p の倍数をふるう
        for (long long q = start; q <= B; q += p) {
            isprime2[q - A] = false;
        }
    }

    // 答え
    long long res = 0;
    for (long long q = A; q <= B; ++q) {
        if (isprime2[q - A]) ++res;
    }
    cout << res << endl;
}

• 解説AC

A を割ると B あまる数

• 式変形に気づけず...

あまりが等しい

• 差の絶対値の約数を求めればよいということに自力で気づけた
• 自力AC

メビウス関数

• 新たな概念（メビウス関数）に引っ張られて指数に着目すればよいだけという単純な部分に気づけなかった...

√(AN) を整数にせよ

• 高校数学でよくやったやつ
• 既にAが平方数であるばあいにもたいおうで

// 素因数分解
// 460 = 2^2 x 5 x 23 の場合
// 返り値は {{2, 2}, {5, 1}, {23, 1}}
vector<pair<long long, long long> > prime_factorize(long long N) {
    // 答えを表す可変長配列
    vector<pair<long long, long long> > res;

    // √N まで試し割っていく
    for (long long p = 2; p * p <= N; ++p) {
        // N が p で割り切れないならばスキップ
        if (N % p != 0) {
            continue;
        }

        // N の素因数 p に対する指数を求める
        int e = 0;
        while (N % p == 0) {
            // 指数を 1 増やす
            ++e;

            // N を p で割る
            N /= p;
        }

        // 答えに追加
        res.emplace_back(p, e);
    }

    // 素数が最後に残ることがありうる
    if (N != 1) {
        res.emplace_back(N, 1);
    }
    return res;
}


int main() {
    long long A;
    cin >> A;
    vector<pair<long long, long long> > aPrimeFactorization = prime_factorize(A);
    long long ans = 1;
    for (auto p : aPrimeFactorization) {
        if (p.second % 2 == 1) {
            ans *= p.first;
        }
    }
    cout << ans << endl;

}