【luoguP1587】[NOI2016]循环之美

首先最好想的条件,(i, j)=1

第二个条件,设一个无限循环小数的循环节长度为l,那么
i \cdot k^l \equiv i (mod \; j)\\ k^l \equiv 1 (mod \; j)
想一下,i的小数部分都是mod \; j以后的结果,乘上k^l是让小数点整体左移,小数部分不会发生改变

因此我们实际上是求这么一个式子
\sum_{i = 1}^n \sum_{j = 1}^m [(i, j) = 1][(j, k) = 1]
接下来就是数学推导
\begin{aligned} \sum_{i = 1}^n \sum_{j = 1}^m [(i, j) = 1][(j, k) = 1] &= \sum_{j = 1}^m \sum_{i = 1}^n [(i, j) = 1][(j, k) = 1]\\ &= \sum_{j = 1}^m [(j, k) = 1] \sum_{i = 1}^n [(i, j) = 1]\\ &= \sum_{j = 1}^m [(j, k) = 1] \sum_{i = 1}^n \sum_{d|i,d|j} \mu(d)\\ &= \sum_{d = 1}^n \mu(d) \lfloor \frac{n}{d} \rfloor \sum_{j = 1}^m [d|j][(j, k) = 1]\\ &= \sum_{d = 1}^n \mu(d) \lfloor \frac{n}{d} \rfloor \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}[(jd, k) = 1]\\ &= \sum_{d = 1}^n \mu(d) \lfloor \frac{n}{d} \rfloor [(d, k) = 1] \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}[(j, k) = 1]\\ \end{aligned}
到这一步,我们将式子拆成两半分析,首先考虑简单一点的式子

f(x) = \sum_{j = 1}^x[(j, k) = 1]​

那么对于一个数a \leq k​,如果(a,k)=1​,那么(a+bk, k) = 1​

所以我们有这么一个式子

f(x) = \lfloor \frac{n}{x} \rfloor f(k) + f(x \; mod \; k) ​

第二个式子是S(x,k) = \sum_{d = 1}^n \mu(d) [(d, k) = 1]​
\begin{aligned} S(x,k) &= \sum_{d = 1}^x \mu(d) [(d, k) = 1]\\ &= \sum_{d=1}^x\mu(d) \sum_{D|d,D|k}\mu(D)\\ &= \sum_{D|k}\mu(D) \sum_{D|d}\mu(d)\\ &= \sum_{D|k}\mu(D) \sum_{d=1}^{ \lfloor \frac{x}{D} \rfloor}\mu(dD) \end{aligned}
d, k​不互质的时候,\mu(dD)=0​,并不会有影响,互质的话我们就可以按照积性函数的性质拆开了
\begin{aligned} S(x,k) &= \sum_{D|k}\mu(D) \sum_{d=1}^{ \lfloor \frac{x}{D} \rfloor}\mu(dD)\\ &= \sum_{D|k}\mu(D) \sum_{d=1}^{ \lfloor \frac{x}{D} \rfloor}\mu(d) \cdot \mu(D)\\ &= \sum_{D|k}\mu(D)^2 \sum_{d=1}^{ \lfloor \frac{x}{D} \rfloor}\mu(d)[(d, D) = 1]\\ &= \sum_{D|k}\mu(D)^2 S(\frac{x}{D}, D) \end{aligned}
然后就开始递归杜教筛了
公式要命(确信)

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a;
    bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = -x;
}

lo n, m, K, ans, f[2020], smu[10000010];

bool flag[10000010];

int mu[10000010], prime[1000010], cnt;

inline int gcd(int a, int b)
{
    int c;
    while(b)
        c = a, a = b, b = c % b;
    return a;
}

map <pair<int, int>, int> mmp;

lo asks(lo x, lo y)
{
    if((y == 1 && x <= 10000000) || (!x))
        return smu[x];
    pair <int, int> tm = make_pair(x, y);
    if(mmp[tm])
        return mmp[tm];
    lo rt = 0;
    if(y == 1)
    {
        rt = 1;
        for(ri i = 2, j; i <= x; i = j + 1)//还记得luogu的模板题目吗
            j = x / (x / i), rt -= (j - i + 1) * asks(x / i, 1); 
    }
    else
    {
        for(ri i = 1; i * i <= y; i ++)
            if(y % i == 0)
            {
                if(mu[i])
                    rt += asks(x / i, i);
                if(i * i != y && mu[y / i])
                    rt += asks(x / (y / i), y / i);
            }
    }
    return mmp[tm] = rt;
}

int main()
{
    re(n), re(m), re(K); flag[1] = 1, mu[1] = 1;
    for(ri i = 2; i <= 10000000; i ++)
    {
        if(!flag[i])
            prime[++ cnt] = i, mu[i] = -1;
        ri d;
        for(ri j = 1; j <= cnt && (d = i * prime[j]) <= 10000000; j ++)
        {
            flag[d] = 1;
            if(i % prime[j] == 0)
                break;
            mu[d] = -mu[i];
        }
    }
    for(ri i = 1; i <= K; i ++)
        f[i] = f[i - 1] + (gcd(i, K) == 1);
    for(ri i = 1; i <= 10000000; i ++)
        smu[i] = smu[i - 1] + mu[i];
    lo no = 0, las = 0;
    for(ri i = 1, j; i <= min(n, m); i = j + 1)
    {
        j = min(n / (n / i), m / (m / i));
        no = asks(j, K);
        ans += 1ll * (no - las) * (n / i) * (((m / i) / K) * f[K] + f[(m / i) % K]);
        //cout << i << ' ' << j << ' ' << las << ' ' << no << ' ' << ans << '\n';
        las = no;
    }
    printf("%lld", ans);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注