破译密码

AcWing-215-破译密码

分析

见《进阶指南》第179页。

实现

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 50010;
int idx, primes[N];
bool mark[N];
int miu[N], sum[N];

void get_miu (int n) { // 线性筛求莫比乌斯函数
    miu[1] = 1;
    for (int i = 2; i <= n; ++ i) {
        if (mark[i] == false) {
            primes[++ idx] = i;
            miu[i] = -1;
        }
        for (int j = 1; primes[j] <= n / i; ++ j) {
            int val = i * primes[j];
            mark[val] = true;
            if (i % primes[j] == 0) {
                miu[val] = 0;
                break;
            }
            miu[val] = -1 * miu[i];
        }
    }
}

int main () {
    get_miu(50000);
    for (int i = 1; i <= 50000; ++ i)
        sum[i] = sum[i - 1] + miu[i];
    int T;
    cin >> T;
    while (T --) {
        int a, b, d;
        cin >> a >> b >> d;
        a /= d, b /= d;
        int n = min(a, b);
        LL res = 0;
        for (int l = 1, r; l <= n; l = r + 1) {
            r = min(n, min(a / (a / l), b / (b / l)));
            res += (LL)(sum[r] - sum[l - 1]) * (a / l) * (b / l);
        }
        cout << res << endl;
    }
    return 0;
}