[SDOI2014]数表

[SDOI2014]数表

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int prime[N], mu[N], ans[N], tree[N], cnt;

bool st[N];

struct Node {
    int id, sigma;

    bool operator < (const Node &T) const {
        return sigma < T.sigma;
    }
}a[N];

struct Ask {
    int n, m, a, id;

    bool operator < (const Ask &T) const {
        return a < T.a;
    }
}ask[N];

void init() {
    mu[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i = 1; i < N; i++) {
        a[i].id = i;
        for(int j = i; j < N; j += i) {
            a[j].sigma += i;
        }
    }
}

int lowbit(int x) {
    return (-x) & x;
}

void update(int x, int value) {
    while(x < N) {
        tree[x] += value;
        x += lowbit(x);
    }
}

int query(int x) {
    int ans = 0;
    while(x) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}

int calc(int n, int m) {
    if(n > m) swap(n, m);
    int ans = 0;
    for(int l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        ans = ans + (n / l) * (m / l) * (query(r) - query(l - 1));
    }
    return ans;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    int Q;
    scanf("%d", &Q);
    for(int i = 1; i <= Q; i++) {
        scanf("%d %d %d", &ask[i].n, &ask[i].m, &ask[i].a);
        ask[i].id = i;
    }
    sort(ask + 1, ask + 1 + Q);
    sort(a + 1, a + N);
    int pos = 1;
    for(int i = 1; i <= Q; i++) {
        while(pos < N && a[pos].sigma <= ask[i].a) {
            for(int j = a[pos].id; j < N; j += a[pos].id) {
                update(j, a[pos].sigma * mu[j / a[pos].id]);
            }
            pos++;
        }
        ans[ask[i].id] = calc(ask[i].n, ask[i].m);
    }
    for(int i = 1; i <= Q; i++) {
        printf("%d\n", ans[i] & ((1ll << 31) - 1));
    }
    return 0;
}