[bzoj 3309] DZY Loves Math

定义 为正整数 所含质因子的最大幂指数, 给定 , 求 . T组询问. (T≤10^4, 1≤a,b≤10^7) 一时看不出 函数的端倪, 但是在外层枚举 , 再反演一发大概是有益的: 发现上式和[bzoj 2693] jzptab有异曲同工之妙. 数据范围也相同.

令 , 则

需要在不高于线性时间内预处理出 的前缀和.

在没有什么思路的情况下, 在看题解 (弃疗) 之前, 我选择用 算法打表找规律......

首先, 发现所有 值都是-1,0,1中的一个.

发现质数和质数的幂的 值为1, 两个互质的数的乘积的 值为-1.

和莫比乌斯函数表放在一起看, 没有发现什么.

对取每个值的数做一做质因数分解. 和 是两个提示性很强的信息. 做出如下归纳: 设 , - 如果所有 相等, 则 . - 如果存在 , 则 .

线性筛, 记录 和 , 就能递推计算出 .

值的计算是本题的难点. 解决之后就可以AC了.

学习了一下题解. 对 的定义式进行分析, 可以证明上述结论.

方便起见, 我们把对象从整数转换到集合. 设 , 则只用考虑所有 的那些 , 每个 对应于集合 , 且 .

我们有以下关系式:

这和 是一致的.

注意到 . 设 , .

当 时, , . 当 时, 于是, 当 , 即所有 均相等时, ; 当 , 即存在 时, .

typedef long long ll;

const int N = 1e7;

int f[N+1], g[N+1], h[N+1];

void sieve()
{
	static bool v[N+1];
	static int p[N+1], ptr;
	
	rep (i, 2, N+1)
	{
		if (!v[i])
		{
			h[i] = f[i] = 1;
			g[i] = i;
			p[ptr++] = i;
		}
		for (int j = 0, t; j < ptr && (t = i*p[j]) <= N; ++j)
		{
			v[t] = true;
			if (i % p[j])
			{
				f[t] = 1;
				g[t] = p[j];
				h[t] = f[i] == 1 ? -h[i] : 0;
			}
			else
			{
				f[t] = f[i] + 1;
				g[t] = g[i] * p[j];
				h[t] = g[t] == t ? 1 : (f[i/g[i]] == f[i] + 1 ? -h[i/g[i]] : 0);
				break;
			}
		}
	}

	rep (i, 2, N+1)
		h[i] += h[i-1];
}

ll solve(int a, int b)
{
	ll ans = 0;
	for (int i = 1, j, c = min(a, b); i <= c; i = j+1)
	{
		int _a = a/i, _b = b/i;
		j = min(a/_a, b/_b);
		ans += 1LL * _a * _b * (h[j] - h[i-1]);
	}
	return ans;
}

int main()
{
	sieve();

	int T;
	scanf("%d", &T);
	while (T--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%lld\n", solve(a, b));
	}
	return 0;
}