洛谷 P1587 题解

admin 2021-08-17 PM 79℃ 0条

题目链接

分析

首先我们可以只计算最简分数。

有一个结论:最简分数 $\dfrac{x}{y}$ 为 $k$ 进制下的纯循环小数 or 整数,当且仅当 $\gcd(y,k)=1$。

这个东西非常的小学奥数,懒得证了(其实是不会)。

所以题目要求的就是:

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

开始推式子:

$$ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^m[i\perp j][j\perp k]=&\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor n/d \rfloor}\sum_{j=1}^{\lfloor m/d \rfloor}[\gcd(jd,k)=1]\\ =&\sum_{d=1}^n[d\perp k]\mu(d)\lfloor\dfrac{n}{d}\rfloor\sum_{j=1}^{\lfloor m/d\rfloor}[j\perp k] \end{aligned} $$

中间有 $\lfloor\dfrac{n}{d}\rfloor$ 和 $\lfloor\dfrac{m}{d}\rfloor$ 看起来可以整除分块。

所以只需要计算其他部分的前缀和就可以了。

设 $f(x)=\sum_{i=1}^x[i\perp k]$,$g(x,k)=\sum_{i=1}^x[i\perp k]\mu(i)$。

首先看 $f(x)$。因为 $\gcd(i,k)=\gcd(i+k,k)$,故有:

$$f(x)=\lfloor\dfrac{x}{k}\rfloor\varphi(k)+f(x \bmod k)$$

可以在 $O(k)$ 时间预处理,$O(1)$ 查询。

再看 $g(x,k)$。

$$ \begin{aligned}g(x,k) =&\sum_{i=1}^x[i\perp k]\mu(i)\\ =&\sum_{d|k}\mu(d)\sum_{i=1}^{\lfloor x/d\rfloor}\mu(id) \end{aligned} $$

如果 $\gcd(i,d)>1$,那么 $\mu(id)=0$,对答案没有贡献;否则 $\mu(id)=\mu(i)\mu(d)$。

$$ \begin{aligned}g(x,k)=&\sum_{d|k}\mu(d)^2\sum_{i=1}^{\lfloor x/d\rfloor}[i\perp d]\mu(i)\\ =&\sum_{d|k}\mu(d)^2g(\lfloor\dfrac{x}{d}\rfloor,d) \end{aligned} $$

递归求解,直到 $k=1$ 的时候有 $g(x,1)=\sum_{i=1}^x\mu(i)$ 也就是 $\mu$ 函数前缀和,杜教筛即可。

复杂度我也不会算,但是拿 map 把 $g$ 记忆化就能跑过去了,但是跑得有点慢。(其实也不是特别慢)

解决

代码:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>

using namespace std;

const int N = 1e7 + 5, K = 2e3 + 5;
int mu[N], smu[N], f[K], prime[N], cnt, phi, n, m, k, _n;
map<pair<int, int>, int> g;
bool isPrime[N];

int gcd(int x, int y)
{
    int r = x % y;
    while (r)
        x = y, y = r, r = x % y;
    return y;
}

void prework()
{
    _n = min((int)pow(n, 2.0 / 3) * 10, n);
    memset(isPrime + 1, true, _n);
    isPrime[1] = false, mu[1] = 1;
    for (int i = 1; i <= _n; i++)
    {
        if (isPrime[i])
            prime[++cnt] = i, mu[i] = -1;
        smu[i] = smu[i - 1] + mu[i];
        int up = _n / i;
        for (int j = 1; j <= cnt && prime[j] <= up; j++)
        {
            isPrime[i * prime[j]] = false;
            if (i % prime[j])
                mu[i * prime[j]] = -mu[i];
            else
                break;
        }
    }
    for (int i = 1; i < k; i++)
    {
        f[i] = f[i - 1];
        if (gcd(i, k) == 1)
            f[i]++;
    }
    int tmp = k;
    phi = k;
    for (int i = 2; i * i <= tmp; i++)
    {
        if (tmp % i)
            continue;
        phi = phi / i * (i - 1);
        while (tmp % i == 0)
            tmp /= i;
    }
    if (tmp > 1)
        phi = phi / tmp * (tmp - 1);
}

int F(int x)
{
    return x / k * phi + f[x % k];
}

int G(int x, int k)
{
    if (k == 1 && x <= _n)
        return smu[x];
    if (x == 0)
        return 0;
    if (g.find(make_pair(x, k)) != g.end())
        return g[make_pair(x, k)];
    int ans = 0;
    if (k == 1)
    {
        ans = x > 1;
        for (int l = 2, r; l <= x; l = r + 1)
        {
            r = min(x / (x / l), x);
            ans -= (r - l + 1) * G(x / l, 1);
        }
    }
    else
    {
        for (int i = 1; i * i <= k; i++)
        {
            if (k % i)
                continue;
            if (mu[i])
                ans += G(x / i, i);
            if (mu[k / i] && i * i != k)
                ans += G(x / (k / i), k / i);
        }
    }
    g[make_pair(x, k)] = ans;
    return ans;
}

int main()
{
    cin >> n >> m >> k;
    prework();
    long long ans = 0;
    for (int l = 1, r, last = 0; l <= n && l <= m; l = r + 1)
    {
        r = min(min(n / (n / l), n), min(m / (m / l), m));
        int cur = G(r, k);
        ans += 1LL * (cur - last) * (n / l) * F(m / l);
        last = cur;
    }
    cout << ans << endl;
    return 0;
}

非特殊说明,本博所有文章均为博主原创。

评论啦~