Description
有一张N×m的数表，其第i行第j列（1 < =i < =N，1 < =j < =m）的数值为
能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。
Input
输入包含多组数据。
输入的第一行一个整数Q表示测试点内的数据组数，接下来Q行，每行三个整数n，m，a(|a| < =10^9)描述一组数据。
Output
对每组数据，输出一行一个整数，表示答案模2^31的值。
Sample Input
4 4 3
10 10 5
Sample Output
148
HINT
1 < =N．m < =10^5 ， 1 < =Q < =2×10^4
题解
假设没有 $a$ 的限制，那么题目就是求 $$sum_{i=1}^nsum_{j=1}^msigma(gcd(i,j))$$
这个 $sigma$ 太鬼辣！我们用 $♂$ 来代替它。
我们提出 $gcd(i,j)$ egin{aligned}ans&=sum_{d=1}^{min{n,m}}♂(d)sum_{i=1}^nsum_{j=1}^m[gcd(i,j)=d]\&=sum_{d=1}^{min{n,m}}♂(d)sum_{i=1}^{leftlfloorfrac{n}{d} ight floor}sum_{j=1}^{leftlfloorfrac{m}{d} ight floor}[gcd(i,j)=1]\&=sum_{d=1}^{min{n,m}}♂(d)sum_{i=1}^{leftlfloorfrac{n}{d} ight floor}sum_{j=1}^{leftlfloorfrac{m}{d} ight floor}sum_{kmid gcd(i,j)}mu(k)\&=sum_{d=1}^{min{n,m}}♂(d)sum_{i=1}^{leftlfloorfrac{n}{d} ight floor}sum_{j=1}^{leftlfloorfrac{m}{d} ight floor}sum_{kmid gcd(i,j)}mu(k)\&=sum_{d=1}^{min{n,m}}♂(d)sum_{k=1}^{minleft{leftlfloorfrac{n}{d} ight floor,leftlfloorfrac{m}{d} ight floor ight}}mu(k)leftlfloorfrac{n}{kd} ight floorleftlfloorfrac{m}{kd} ight floorend{aligned}
令 $T=kd$ ，枚举 $T$ $$ans=sum_{T=1}^{min{n,m}}leftlfloorfrac{n}{T} ight floorleftlfloorfrac{m}{T} ight floorsum_{kmid T}♂(k)muleft(frac{T}{k} ight)$$
我们让后面那个狄利克雷卷积形式记作 $F(T)$ $$ans=sum_{T=1}^{min{n,m}}F(T)leftlfloorfrac{n}{T} ight floorleftlfloorfrac{m}{T} ight floor$$
现在就好求了，我们可以用枚举因数的方法来算出函数 $F$ 的值。
现在回到原问题，我们发现 $a$ 的约束还是不好操作。但我们想对于一个询问中的 $a$ 只有 $♂(d)leq a$ 的值才会对其有影响。我们考虑离线询问，将 $a$ 从小到大排序。将数值 $i$ 按 $♂(i)$ 的大小排序。枚举因数用树状数组维护前缀。
1 //It is made by Awson on 2018.1.25 2 #include <set> 3 #include <map> 4 #include <cmath> 5 #include <ctime> 6 #include <queue> 7 #include <stack> 8 #include <cstdio> 9 #include <string> 10 #include <vector> 11 #include <cstdlib> 12 #include <cstring> 13 #include <iostream> 14 #include <algorithm> 15 #define LL long long 16 #define Abs(a) ((a) < 0 ? (-(a)) : (a)) 17 #define Max(a, b) ((a) > (b) ? (a) : (b)) 18 #define Min(a, b) ((a) < (b) ? (a) : (b)) 19 #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b)) 20 #define writeln(x) (write(x), putchar(' ')) 21 #define lowbit(x) ((x)&(-(x))) 22 using namespace std; 23 const int N = 1e5; 24 void read(int &x) { 25 char ch; bool flag = 0; 26 for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar()); 27 for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar()); 28 x *= 1-2*flag; 29 } 30 void write(int x) { 31 if (x > 9) write(x/10); 32 putchar(x%10+48); 33 } 34 35 int q, ans[N+5], sig[N+5], mu[N+5]; 36 struct query { 37 int n, m, a, id; 38 bool operator < (const query &b) const { 39 return a < b.a; 40 } 41 }a[N+5]; 42 struct sigma { 43 int a, id; 44 bool operator < (const sigma &b) const { 45 return a < b.a; 46 } 47 }b[N+5]; 48 struct bittree { 49 int c[N+5]; 50 void add(int x, int val) {for (; x <= N; x += lowbit(x)) c[x] += val; } 51 int query(int x) { 52 int ans = 0; 53 for (; x; x -= lowbit(x)) ans += c[x]; 54 return ans; 55 } 56 }T; 57 58 void get_pre() { 59 int isprime[N+5], prime[N+5], tot = 0, sumd[N+5], prod[N+5]; 60 memset(isprime, 1, sizeof(isprime)); isprime[1] = 0, mu[1] = sig[1] = 1; b[1].id = b[1].a = 1; 61 for (int i = 2; i <= N; i++) { 62 if (isprime[i]) prime[++tot] = i, mu[i] = -1, sig[i] = 1+i, sumd[i] = 1+i, prod[i] = i; 63 for (int j = 1; j <= tot && i*prime[j] <= N; j++) { 64 isprime[i*prime[j]] = 0; 65 if (i%prime[j]) mu[i*prime[j]] = -mu[i], sig[i*prime[j]] = sig[i]*sig[prime[j]], sumd[i*prime[j]] = 1+prime[j], prod[i*prime[j]] = prime[j]; 66 else {mu[i*prime[j]] = 0, prod[i*prime[j]] = prod[i]*prime[j], sumd[i*prime[j]] = sumd[i]+prod[i*prime[j]], sig[i*prime[j]] = sig[i]/sumd[i]*sumd[i*prime[j]]; break; } 67 } 68 b[i].id = i, b[i].a = sig[i]; 69 } 70 } 71 int solve(int n, int m) { 72 if (n > m) Swap(n, m); int ans = 0; 73 for (int i = 1, last; i <= n; i = last+1) { 74 last = Min(n/(n/i), m/(m/i)); ans += (n/i)*(m/i)*(T.query(last)-T.query(i-1)); 75 } 76 return ans; 77 } 78 void work() { 79 get_pre(); read(q); 80 for (int i = 1; i <= q; i++) read(a[i].n), read(a[i].m), read(a[i].a), a[i].id = i; 81 sort(a+1, a+1+q); sort(b+1, b+1+N); 82 for (int i = 1, last = 1; i <= q; i++) { 83 while (last < N && b[last].a <= a[i].a) { 84 for (int j = 1; j*b[last].id <= N; j++) if (mu[j]) T.add(j*b[last].id, mu[j]*b[last].a); 85 last++; 86 } 87 ans[a[i].id] = solve(a[i].n, a[i].m); 88 } 89 for (int i = 1; i <= q; i++) writeln(ans[i]&(~0u>>1)); 90 } 91 int main() { 92 work(); 93 return 0; 94 }