[BZOJ3529][Sdoi2014]数表

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
	if(Head == Tail) {
		int l = fread(buffer, 1, BufferSize, stdin);
		Tail = (Head = buffer) + l;
	}
	return *Head++;
}
int read() {
	int x = 0, f = 1; char c = Getchar();
	while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = Getchar(); }
	while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = Getchar(); }
	return x * f;
}

#define maxn 100010

const int MOD = 2147483647;
int prime[maxn], cp, mu[maxn], smu[maxn], remain[maxn], f[maxn], Ord[maxn];
bool vis[maxn];
bool cmp(int a, int b) { return f[a] < f[b]; }
void init() {
	mu[1] = 1; f[1] = 1;
	for(int i = 2; i < maxn; i++) {
		if(!vis[i]) prime[++cp] = i, mu[i] = -1, f[i] = 1 + i, remain[i] = 1;
		for(int j = 1; i * prime[j] < maxn && j <= cp; j++) {
			vis[i*prime[j]] = 1;
			if(i % prime[j] == 0) {
				mu[i*prime[j]] = 0;
				f[i*prime[j]] = f[i] + f[remain[i]] * (i / remain[i] * prime[j]);
				remain[i*prime[j]] = remain[i];
				break;
			}
			mu[i*prime[j]] = -mu[i];
			f[i*prime[j]] = f[i] * (prime[j] + 1);
			remain[i*prime[j]] = i;
		}
		smu[i] = smu[i-1] + mu[i];
	}
	for(int i = 1; i < maxn; i++) Ord[i] = i;
	sort(Ord + 1, Ord + maxn, cmp);
	return ;
}

struct Que {
	int n, m, a, id;
	Que() {}
	Que(int _1, int _2, int _3, int _4): n(_1), m(_2), a(_3), id(_4) {}
	bool operator < (const Que& t) const { return a < t.a; }
} qs[maxn];
int Ans[maxn];

int S[maxn];
void Add(int x, int v) {
	for(; x < maxn; x += x & -x) S[x] += v;
	return ;
}
int Sum(int x) {
	int ans = 0;
	for(; x; x -= x & -x) ans += S[x];
	return ans;
}

int main() {
	init();
	
	int T = read();
	for(int i = 1; i <= T; i++) {
		int n = read(), m = read(), a = read();
		qs[i] = Que(n, m, a, i);
	}
	
	sort(qs + 1, qs + T + 1);
	int j = 1;
	for(int q = 1; q <= T; q++) {
		while(j < maxn && f[Ord[j]] <= qs[q].a) {
			for(int d = 1; Ord[j] * d < maxn; d++) Add(Ord[j] * d, f[Ord[j]] * mu[d]);
			j++;
		}
		int n = qs[q].n, m = qs[q].m; if(n > m) swap(n, m);
		for(int i = 1, lst; i <= n; i = lst + 1) {
			lst = min(n / (n / i), m / (m / i));
			Ans[qs[q].id] += (n / i) * (m / i) * (Sum(lst) - Sum(i - 1));
		}
	}
	
	for(int i = 1; i <= T; i++) printf("%d\n", Ans[i] & MOD);
	
	return 0;
}