题解 P8151【彼岸 | To See the Next Part of the Dream】

· · 题解

P8151 彼岸 | To See the Next Part of the Dream 解题报告：

更好的阅读体验

下文称奇数集合为 \mathbb{O}。

题意

对于一个长度为 2^n 的排列 1,2,\cdots,2^n，令置换 P 为 x\mapsto 2x\pmod{2^n+1}，令 f(n) 为 P^0,P^1,\cdots,P^{n-1} 的不动点数量之和，求 f 的前缀和。

1\leqslant n\leqslant 10^{10}

分析

思路曲折复杂，需要一定的熟练度与技巧的题。

将置换拆成若干个环，可以发现点 x 在长度为 l 约数的环内当且仅当 (2^l-1)x\equiv0\pmod{2^n+1}，也就是：

\frac{2^n+1}{\gcd(2^n+1,2^l-1)}\mid x

然后联想到经典结论 \gcd(x^a-1,x^b-1)=x^{\gcd(a,b)}-1，于是考虑向其转化：

\gcd(2^n+1,2^l-1)=\gcd(\frac{2^{2n}-1}{2^n-1},2^l-1)=\frac{2^{\gcd(2n,l)}-1}{2^{\gcd(n,l)}-1}

令 t_l 为长度为 l 的约数的环数量（显然 l 是 2n 的因数，因为 2^{2n}l=(2^n+1)(2^n-1)l+l\equiv l\pmod{2^n+1}），那么：

若 \gcd(2n,l)=\gcd(n,l)，那么 2^n+1\mid x，此时 t_l=0。

否则，\gcd(2n,l)=2\gcd(n,l)，那么 \dfrac{2^n+1}{2^{\gcd(n,l)}-1}\mid x，那么 t_l=2^{\gcd(n,l)}。

也就是说 t_l=\begin{cases}0&\gcd(2n,l)=\gcd(n,l)\\2^{\gcd(n,l)}&\text{otherwise}\end{cases}

令 p 为 n 分解质因数有多少个 2，那么 t_l 非零当且仅当 2^{p+1}\mid l。

由于环长是 2n 的约数而不是 n 的约数，走 n 步之后每个环都一定走了一半（原因是造成贡献的环长的二幂次至少是 2^{p+1}，走 2n 步走完的完整环数量为奇数），那么我们就可以令 g(n) 为 P^0,P^1,\cdots,P^{2n-1} 的不动点数量，那么有 f(n)=\sum\frac{g(n)+2^n}{2}。

我们将上面的”为 l 约数“莫反，并设 n=2^ab：

下面要用到的一个式子：\sum_{k=1}^n\mu(k)\lfloor\frac{n}{k}\rfloor=\sum_{d=1}^n\sum_{k\mid d}\mu(k)=1。

g(n)=\sum_{k=1}^{b}\lfloor\frac{2n}{k}\rfloor\sum_{d\mid k\times 2^{a+1}}2^{\gcd(d,b)2^a}\mu(\frac{k}{d})\\=\sum_{p\mid b}2^{2^ap}\sum_{k=1}^{\frac{b}{p}}\lfloor\frac{b}{pk}\rfloor\sum_{d\mid k}\mu(\frac{k}{d})\sum_{z\mid d,z\mid\frac{b}{p}}\mu(z)\\=\sum_{p\mid b}2^{2^ap}\sum_{z\mid\frac{b}{p}}\mu(z)\sum_{d=1}^{\frac{b}{pz}}\sum_{k=1}^{\lfloor\frac{b}{pzd}\rfloor}\mu(k)\lfloor\frac{b}{pzdk}\rfloor\\=\sum_{p\mid b}2^{2^ap}\sum_{z\mid\frac{b}{p}}\mu(z)\sum_{d=1}^{\frac{b}{pz}}1=\sum_{p\mid b}2^{2^ap}\sum_{z\mid\frac{b}{p}}\mu(z)\frac{b}{pz}\\=\sum_{p\mid b}2^{2^ap}\varphi(\frac{b}{p})=\sum_{p\mid n,p\in\mathbb{O}}2^{\frac{n}{p}}\varphi(p)

继续推：

\sum_{i=1}^ng(i)=\sum_{i=1}^n\sum_{p\mid n,p\in\mathbb{O}}2^{\frac{n}{p}}\varphi(p)\\=\sum_{d=1}^n2^d\sum_{1\leqslant p\leqslant \lfloor\frac{n}{d}\rfloor,p\in\mathbb{O}}\varphi(p)

记 h(n)=\sum_{i=1}^n[i\in\mathbb{O}]\varphi(i),p(n)=\sum_{i=1}^n\varphi(i)，那么有：

g(i)=\sum_{d=1}^n 2^dh(\lfloor\frac{n}{d}\rfloor)\\h(n)=p(n)-\sum_{i=1}^n[i\notin\mathbb{O}]\varphi(i)=p(n)-\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}[i\in\mathbb{O}]\varphi(2i)-\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}[i\notin\mathbb{O}]\varphi(2i)\\=p(n)-\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}[i\in\mathbb{O}]\varphi(i)-2\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}[i\notin\mathbb{O}]\varphi(i)\\=p(n)-h(\lfloor\frac{n}{2}\rfloor)-2(p(\lfloor\frac{n}{2}\rfloor)-h(\lfloor\frac{n}{2}\rfloor))=p(n)-2p(\lfloor\frac{n}{2}\rfloor)+h(\lfloor\frac{n}{2}\rfloor)

归纳可以证明 h(n)=p(n)-\sum_{i=1}^{\lfloor\log_2 n\rfloor}p(\lfloor\frac{n}{2^i}\rfloor)。

由于杜教筛是块筛（即其可以筛出 x=\lfloor\frac{n}{1}\rfloor,\lfloor\frac{n}{2}\rfloor,\cdots,\lfloor\frac{n}{n}\rfloor 时函数前缀和的值），所以我们进行一次杜教筛，然后暴力算就好了。

复杂度 O(n^{\frac{2}{3}}+\sqrt n\log n)。

代码

写的时候偷懒用了 map，实现的也不太精细，不过还是勉强过了。

#include<stdio.h>
#include<map>
using namespace std;
const int maxn=5000005,mod=998244353,inv2=(mod+1)/2;
long long L,R;
int ps;
int c[maxn],p[maxn],phi[maxn],sum[maxn];
map<long long,int>mp;
int ksm(int a,long long b){
    int res=1;
    while(b){
        if(b&1)
            res=1ll*res*a%mod;
        a=1ll*a*a%mod,b>>=1;
    }
    return res;
}
void sieve(int n){
    c[1]=phi[1]=sum[1]=1;
    for(int i=2;i<=n;i++){
        if(c[i]==0)
            p[++ps]=i,phi[i]=i-1;
        for(int j=1;j<=ps&&i*p[j]<=n;j++){
            c[i*p[j]]=1;
            if(i%p[j]==0){
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            phi[i*p[j]]=phi[i]*(p[j]-1);
        }
        sum[i]=(sum[i-1]+phi[i])%mod;
    }
}
int calcp(long long n){
    if(n<=5000000)
        return sum[n];
    if(mp.count(n))
        return mp[n];
    int res=1ll*(n%mod)*(n%mod+1)%mod*inv2%mod;
    long long l=2,r;
    while(l<=n)
        r=n/(n/l),res=(res-1ll*(r-l+1)%mod*calcp(n/l)%mod+mod)%mod,l=r+1;
    return mp[n]=res;
}
int calch(long long n){
    int res=calcp(n);
    n>>=1;
    while(n)
        res=(res-calcp(n)+mod)%mod,n>>=1;
    return res;
}
int calcf(long long n){
    long long l=1,r;
    int res=0,lst=0;
    while(l<=n){
        r=n/(n/l);
        int now=(ksm(2,r+1)-2+mod)%mod;
        res=(res+1ll*(now-lst+mod)*calch(n/l))%mod;
        lst=now;
        l=r+1;
    }
    return 1ll*(0ll+res+ksm(2,n+1)-2+mod)*inv2%mod;
}
int main(){
    sieve(5000000);
    scanf("%lld%lld",&L,&R);
    printf("%d\n",(calcf(R)-calcf(L-1)+mod)%mod);
    return 0;
}