题解 P6210 【「SWTR-04」Easy Math Problems】

· · 题解

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

设该式子的值为 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 = "")