看Yveh的题解，这道题卡了好长时间，一直不明白为什么要······算了当时太naive我现在都不好意思说了
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 1E5;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
}
bool np[N + 3];
int prime[N + 3], mu[N + 3], f[N + 3], exmin[N + 3], bit[N + 3], up = 0;
void shai() {
mu[1] = f[1] = 1; int num = 0;
for(int i = 2; i <= N; ++i) {
if (!np[i]) {
mu[i] = -1;
prime[++num] = i;
f[i] = 1 + i;
exmin[i] = 1;
}
for(int j = 1; j <= num; ++j) {
int t = prime[j] * i; if (t > N) break;
np[t] = 1;
if (i % prime[j] == 0) {
mu[t] = 0;
f[t] = exmin[i] + prime[j] * f[i];
exmin[t] = exmin[i];
break;
}
mu[t] = -mu[i];
f[t] = f[i] * (1 + prime[j]);
exmin[t] = f[i];
}
}
}
int Qsum(int x) {
int ret = 0;
for(; x; x -= x & -x)
ret += bit[x];
return ret;
}
void add(int x, int s) {
for(; x <= up; x += x & -x)
bit[x] += s;
}
void update(int d, int s) {
for(int i = d, j = 1; i <= up; i += d, ++j)
add(i, s * mu[j]);
} struct node1 {int n, m, a, id;} Q[N + 3];
struct node2 {int f, id;} F[N + 3];
bool cmp1(node1 X, node1 Y) {return X.a < Y.a;}
bool cmp2(node2 X, node2 Y) {return X.f < Y.f;} int ans[N + 3];
int main() {
shai();
int T;
read(T);
for(int i = 1; i <= T; ++i) {
read(Q[i].n); read(Q[i].m); read(Q[i].a);
Q[i].id = i;
if (Q[i].n > Q[i].m) swap(Q[i].n, Q[i].m);
up = max(up, Q[i].m);
}
sort(Q + 1, Q + T + 1, cmp1);
for(int i = 1; i <= up; ++i)
F[i].f = f[i], F[i].id = i;
sort(F + 1, F + up + 1, cmp2); int n, m, a, tmp = 1;
for(int i = 1; i <= T; ++i) {
n = Q[i].n; m = Q[i].m; a = Q[i].a;
while (tmp <= up && F[tmp].f <= a)
update(F[tmp].id, F[tmp].f), ++tmp;
int ret = 0;
for(int j = 1, la = 1; j <= n; j = la + 1) {
la = min(n / (n / j), m / (m / j));
ret += (Qsum(la) - Qsum(j - 1)) * (n / j) * (m / j);
}
ans[Q[i].id] = ret & ((1u << 31) - 1);
}
for(int i = 1; i <= T; ++i)
printf("%d\n", ans[i]); return 0;
}
不容易啊QuQ