C++

[NOI2016] 循环之美


记录一部分的推导过程


\(k\)进制下,某个合法纯循环数的分数表示为\(\frac{x}y,(x\le n,y\le m)\),其循环节长度为\(L\),有约束

\[ \begin{cases} (x,y)=1\\ \dfrac{xk^L}{y}-\lfloor\dfrac{xk^L}{y}\rfloor=\dfrac{x}{y}-\lfloor\dfrac{x}{y}\rfloor\rightarrow xk^L\equiv x\pmod y\rightarrow k\equiv 1\pmod y \end{cases}\\ \Downarrow\\ (x,y)=1,k\equiv 1\pmod y\rightarrow (x,y)=(k,y)=1 \]

因此可以得出一个算法:答案为\(\sum_{i=1}^n\sum_{j=1}^m[(i,j)=1][(j,k)=1]\)


进行化简(fán)

\[ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^m[(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_{j=1}^m[(j,k)=1]\sum_{d|j}\mu(d)\lfloor\frac{n}{d}\rfloor\\ &=\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(n)=\sum_{i=1}^n[(i,k)=1]\)\(f(n)=\lfloor\frac{n}k\rfloor\varphi(k)+f(n\bmod k)\),只需要暴力计算前\(k\)项即可。

于是,考虑对\(d\)关于\(n,m\)整除分块,问题转化到求出\(\sum_{d=1}^n\mu(d)[(d,k)=1]\)的值,不妨记为\(g(n,k)\)

变形继续

\[ \begin{aligned} g(n,k)&=\sum_{d=1}^n\mu(d) \sum_{p|d,p|k}\mu(p)\\ &=\sum_{p|k}\mu(p)\sum_{p|d}^n\mu(d) \\ &=\sum_{p|k}\mu(p)\sum_{d=1}^{\lfloor\frac{n}p\rfloor}\mu(dp) \\ &=\sum_{p|k}\mu(p)\sum_{d=1}^{\lfloor\frac{n}p\rfloor}\mu(d)\mu(p) [(d,p)=1]\\ &=\sum_{p|k}\mu^2(p)g(\lfloor\frac{n}p\rfloor,p) \end{aligned} \]

钦定两个边界\(g(0,)=0,g(n,1)=\sum_{i=1}^n\mu(i)\)(杜教筛)。复杂度莫名的\(O(n^{\frac{1}2}k+n^{\frac{2}3})\)

\[ \begin{aligned} &T(0,)=T(,0)=1\\ &T(n,k)=\sum_{p|k}T(\lfloor\frac{n}p\rfloor,p) \end{aligned} \]


总结:回忆起了很多东西。

#include <bits/stdc++.h>
using namespace std;
const int PN=1e6+10;

int ctp,pri[PN],phi[PN],mu[PN],smu[PN];
bool vis[PN];

void init() {
    for(int i=2; i<PN; ++i) {
        if(!vis[i]) {
            pri[++ctp]=i;
            phi[i]=i+(mu[i]=-1);
        }
        for(int j=1; j<=ctp&&i*pri[j]<PN; ++j) {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0) {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            phi[i*pri[j]]=phi[i]*(pri[j]-1);
            mu[i*pri[j]]=0-mu[i];
        }
    }
    mu[1]=1;
    for(int i=1; i<PN; ++i) smu[i]=smu[i-1]+mu[i];
}

int n,m,k;
int cnt,dvs[2001],f[2001];

unordered_map<int,long long> sum_base;

long long F(int n) {return n/k*phi[k]+f[n%k];}
long long sum(int n) {
    if(n<PN) return smu[n];
    if(sum_base.count(n)) return sum_base[n];
    long long S=1;
    for(int l=2,r; l<=n; l=r+1) {
        r=n/(n/l);
        S-=sum(n/l)*(r-l+1);
    }
    sum_base[n]=S;
    return S;
}
long long calc(int n,int k) {
    if(!n) return 0;
    if(k==1) return sum(n);
    long long ret=0;
    for(int i=1; i<=cnt&&dvs[i]<=k; ++i) 
    if(k%dvs[i]==0&&mu[dvs[i]]) {
        ret+=calc(n/dvs[i],dvs[i])*mu[dvs[i]]*mu[dvs[i]];
    }
    return ret;
}


int main() {
    init();
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1; i<=k; ++i) {
        if(k%i==0) dvs[++cnt]=i;
        f[i]=f[i-1]+(__gcd(i,k)==1);
    }
    long long ans=0,lst=0,tmp;
    for(int l=1,r; l<=n&&l<=m; l=r+1,lst=tmp) {
        tmp=calc(r=min(n/(n/l),m/(m/l)),k);
        ans+=(tmp-lst)*(n/l)*F(m/l);
    }
    printf("%lld\n",ans);
    return 0;
}

作者:nostabaka,发布于:2019/05/15
原文:https://www.cnblogs.com/nosta/p/10867730.html