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
2
4 4 3
10 10 5
Sample Output
20
148
HINT
1 < =N．m < =10^5 ，1 < =Q <=2×10^4
题解
先推试子
先不考虑a
设$F(i)$为i的约数和
设$g(i)=\sum_{i|d}{\mu(\frac{d}{i})\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor}$
可以轻松的得
$$ \sum_{i=1}^{n}{F(i)g(i)} = \sum_{d=1}^{n}{\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor \sum_{i|d}{F(i)\mu(\frac{d}{i})}} $$
对于$\sum_{i|d}{F(i)\mu(\frac{d}{i})}$想怎么求就怎么求
而如果有a
那么我们可以离线，树状数组维护就可以
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
unsigned int tmp1[100005], tmp2[100005], s[100005];
int prime[100005], tot;
int mu[100005];
bool isnprime[100005];
int a[100005];
int N = 100000;
int comp(const int &c, const int &b)
{
return s[c] < s[b];
}
void Get_Fun()
{
s[1] = mu[1] = 1;
tmp1[1] = tmp2[1] = 0;
for (int i = 2; i <= N; i++)
{
if (!isnprime[i])
{
prime[++tot] = i;
mu[i] = -1;
tmp1[i] = i + 1, tmp2[i] = i;
s[i] = i + 1;
}
for (int j = 1; j <= tot; j++)
{
if (i * prime[j] > N)
break;
isnprime[i * prime[j]] = 1;
if (i % prime[j] == 0)
{
mu[i * prime[j]] = 0;
s[i * prime[j]] = s[i] / tmp1[i] * (tmp1[i] + tmp2[i] * prime[j]);
tmp1[i * prime[j]] = tmp1[i] + tmp2[i] * prime[j];
tmp2[i * prime[j]] = tmp2[i] * prime[j];
break;
}
mu[i*prime[j]] = -mu[i];
s[i * prime[j]] = s[i] * s[prime[j]];
tmp1[i * prime[j]] = prime[j] + 1;
tmp2[i * prime[j]] = prime[j];
}
}
for (int i = 1; i <= N; i++)
a[i] = i;
sort(a + 1, a + N + 1, comp);
}
unsigned int Sum[100005];
#define lowbit(_) ((_) & (-_))
void add(int a, int b)
{
for (int i = a; i <= N; i += lowbit(i))
Sum[i] += b;
}
unsigned int Query(int a)
{
unsigned int ans = 0;
for (int i = a; i > 0; i -= lowbit(i))
ans += Sum[i];
return ans;
}
struct data
{
int n, m, a, ID;
bool operator<(const data &b) const
{
return a < b.a;
}
} Q[20005];
unsigned int ans[20005];
unsigned int Query(data S)
{
if (S.n > S.m)
swap(S.n, S.m);
unsigned int ans = 0,last;
for (int i = 1; i <= S.n; i = last + 1)
{
last = min(S.n / (S.n / i), S.m / (S.m / i));
ans += (Query(last) - Query(i - 1)) * (S.n / i) * (S.m / i);
}
return ans;
}
int main(int argc, char const *argv[])
{
freopen("sdoi2014shb.in","r",stdin);
freopen("sdoi2014shb.out","w",stdout);
int T;
Get_Fun();
scanf("%d", &T);
for (int i = 1; i <= T; i++)
scanf("%d%d%d", &Q[i].n, &Q[i].m, &Q[i].a), Q[i].ID = i;
sort(Q + 1, Q + T + 1);
for (int i = 1, j = 1; i <= T; i++)
{
while (s[a[j]] <= Q[i].a && j <= N)
{
for (int k = 1; k * a[j] <= N; k++)
add(k * a[j], s[a[j]] * mu[k]);
j++;
}
ans[Q[i].ID] = Query(Q[i]);
}
for (int i = 1; i <= T; i++)
{
printf("%d\n",((ans[i]<<1)>>1));
}
return 0;
}