自动搬运

查看原文

来自洛谷，原作者为

	Leasier 我们所知的是沧海一粟，我们所不知的是汪洋大海。

搬运于2025-08-24 22:18:34，当前版本为作者最后更新于2020-11-29 21:29:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑化简第二问所求式子。

设该式子的值为 $g(n, r, c) - g(n, l - 1, c)$，则需要化简 $g$ 函数。

$g(n, m, k) = \displaystyle\sum_{i = 1}^m [\gcd(i, n) \leq k]$

$ = \displaystyle\sum_{d \mid n}^k \displaystyle\sum_{i = 1}^m [\gcd(i, n) = d]$

$ = \displaystyle\sum_{d \mid n}^k \displaystyle\sum_{i = 1}^{\lfloor \frac{m}{d} \rfloor} [\gcd(i, \frac{n}{d}) = 1]$

设第二层 $\sum$ 的值为 $f(\frac{n}{d}, \lfloor \frac{m}{d} \rfloor)$，则需要化简 $f$ 函数。

$f(n, k) = \displaystyle\sum_{i = 1}^k [\gcd(i, n) = 1]$

$ = \displaystyle\sum_{i = 1}^k \sum_{d\ | \gcd(i, n)} \mu(d)$

$ = \displaystyle\sum_{d \mid n} \mu(d) \lfloor \frac{k}{d} \rfloor$

对于第一问，考虑二分答案。

我们可以先消除所有长度为 $n$ 的 $\gcd$ 周期的影响（单个周期为 $g(n, n, c)$），从而使二分答案范围降低为 $1 \sim n$，然后进行二分答案，最后再将整周期的贡献加上即可。时间复杂度还是不会算。

具体细节见代码注释。

代码：

import math

def mu(n):
	ans = 1
	i = 2
	while i * i <= n:
		if n % i == 0:
			n //= i
			if n % i == 0:
				return 0
			ans = -ans
		i += 1
	if n > 1:
		ans = -ans
	return ans

def f_function(n, k):
	t = min(int(math.sqrt(n)), k)
	ans = 0
	for i in range(1, t + 1):
		if n % i == 0:
			ans += mu(i) * (k // i)
			if i * i != n and n // i <= k:
				ans += mu(n / i) * (k // (n // i))
	return ans

def g(n, m, k):
	t = min(int(math.sqrt(n)), k)
	ans = 0
	for i in range(1, t + 1):
		if n % i == 0:
			ans += f_function(n // i, m // i)
			if i * i != n and n // i <= k:
				ans += f_function(i, m // (n / i))
	return ans

def search(n, m, k):
	l = 1
	r = n
	while l < r:
		mid = (l + r) >> 1
		if g(n, mid, m) < k:
			l = mid + 1
		else:
			r = mid;
	return l

n, c, f, l, r = map(int, input().split())
x = g(n, n, c)
if f % x == 0: # 整周期，可能会出现实际端点在 1 ~ n 中的情况。
	y = (f // x - 1) * n
	f = x
else:
	y = f // x * n
	f %= x
print(search(n, c, f) + y)
print(g(n, r, c) - g(n, l - 1, c), end = "")