BZOJ 3529 [Sdoi2014]数表

多组询问，每次询问给出 N、M、a，求满足  的上式值。

不考虑 a 的限制，按照一般的反演套路

令  

令    (反向枚举 )

定义函数 ，并且令   （狄利克雷卷积）

如果没有 a 限制的话，时间复杂度是 

如果加上 a 限制的话，首先线性预处理  [如何线性预处理]，将询问按照 a 的大小排序，然后每次将  的  更新到当前询问的 ，然后数论分块  时间求出每一次询问的值。时间复杂度 

AC代码

#include <bits/stdc++.h>
#define ll long long //T了就换int 试试
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e5 + 5;//用板子前先改范围
//const ll mod = 2147483648;

bool check[MAXN];//值为 false 表示素数，值为 true 表示非素数
//int phi[MAXN];//欧拉函数表
int prime[MAXN];//连续素数表
int mu[MAXN + 10];//莫比乌斯函数
int tot;//素数的个数（从0开始
//ll sub[MAXN];
ll sd[MAXN], sp[MAXN];
void jzk()
{
	//memset(check, false, sizeof(check));
	//phi[1] = 1;
	mu[1] = 1;
	sd[1] = 1;
	tot = 0;
	for (int i = 2; i < MAXN; i++)
	{
		if (!check[i])
		{
			prime[tot++] = i;
			//phi[i] = i - 1;
			mu[i] = -1;
			sd[i] = i + 1;
			sp[i] = i + 1;
		}
		for (int j = 0; j < tot; j++)
		{
			if (i * prime[j] >= MAXN)
				break;
			check[i * prime[j]] = true;
			if (i % prime[j] == 0)
			{
				//phi[i * prime[j]] = phi[i] * prime[j];
				mu[i * prime[j]] = 0;
				sp[i * prime[j]] = (sp[i] * prime[j] + 1);//% mod;
				sd[i * prime[j]] = (sd[i] / sp[i] * sp[i * prime[j]]);//% mod;
				break;
			}
			else
			{
				//phi[i * prime[j]] = phi[i] * (prime[j] - 1);
				mu[i * prime[j]] = -mu[i];
				sd[i * prime[j]] = (sd[i] * sd[prime[j]]);//% mod;
				sp[i * prime[j]] = (1 + prime[j]);//% mod;
			}
		}
	}
	//for (int i = 1; i < MAXN; i++)
		// mu[i] = (mu[i] + mod) % mod;
}
struct node
{
	ll n;
	ll m;
	ll a;
	int id;
}in[20005];
ll ans[20005];
ll c[MAXN];
int lowbit(int k)
{
	return k & (-k);
}
void upd(int k, ll val)
{
	while (k < MAXN)
	{
		c[k] = (c[k] + val);//% mod;
		k += lowbit(k);
	}
}
ll query(int k)
{
	ll ans = 0;
	while (k)
	{
		ans = (ans + c[k]);//% mod;
		k -= lowbit(k);
	}
	return ans;
}
#define Pair pair<ll,int>
Pair tt[MAXN];
int cmp(node q, node w) {
	return q.a < w.a;
}
int cmp1(Pair q, Pair w) {
	return q.first < w.first;
}
int main()
{
	jzk();
	int T;
	sc("%d", &T);
	for (int i = 0; i < T; i++)
	{
		sc("%lld%lld%lld", &in[i].n, &in[i].m, &in[i].a);
		in[i].id = i;
	}
	sort(in, in + T, cmp);
	for (int i = 1; i < MAXN; i++)
	{
		tt[i].first = sd[i];
		tt[i].second = i;
	}
	sort(tt + 1, tt + MAXN, cmp1);
	int now = 1;
	for (int i = 0; i < T; i++)
	{
		while (now <= 1e5 && tt[now].first <= in[i].a)
		{
			for (int i = tt[now].second, cnt = 1; i < MAXN; i += tt[now].second, cnt++)
				upd(i, mu[cnt] * tt[now].first);//% mod);
			now++;
		}
		ll res = 0, j;
		ll n = in[i].n, m = in[i].m;
		ll minn = min(n, m);
		for (ll i = 1; i <= minn; i = j + 1)
		{
			j = min(n / (n / i), m / (m / i));
			res = (res + (n / i) * (m / i) * (query(j) - query(i - 1)));
		}
		ans[in[i].id] = res;
	}
	for (int i = 0; i < T; i++)
		pr("%lld\n", ans[i] & 2147483647);// + mod) % mod);
}
/*
5
4 4 1
4 4 2
4 4 3
4 4 4
4 4 5
*/