P7486 「Stoi2031」彩虹题解

_fairytale_ · 2025-02-12 18:59:47 · 题解

题解区查询怎么都是根号 \log 的？？？？

考虑取离散对数，求出模 32465177 意义下的原根 g=3，同时把询问差分成四个前缀，问题变成求：

A=\sum_{i}\sum_{j}\text{lcm}(i,j)\log \text{lcm}(i,j)

然后 g^A 即为答案。

随便推点式子（下取整省略不写）：

\begin{aligned} &\sum_i\sum_j\text{lcm}(i,j)\log \text{lcm}(i,j)\\ =&\sum_i\sum_j\dfrac{ij}{\gcd(i,j)}(\log i+\log j-\log \gcd(i,j))\\ =&\sum_d\sum_i\sum_j[d=\gcd(i,j)]\dfrac{ij}{d}(\log i+\log j-\log d)\\ =&\sum_d\sum_{i=1}^{\frac{l}{d}}\sum_{j=1}^{\frac{r}{d}}[\gcd(i,j)=1]ijd(\log id+\log jd-\log d)\\ =&\sum_d\sum_{i=1}^{\frac{l}{d}}\sum_{j=1}^{\frac{r}{d}}\sum_{e\mid \gcd(i,j)}\mu(e)ijd(\log id+\log jd-\log d)\\ =&\sum_dd\sum_e\mu(e)e^2\sum_{i=1}^{\frac{l}{de}}\sum_{j=1}^{\frac{r}{de}}ij(\log ide+\log jde-\log d)\\ =&\sum_{T=de}T\sum_{e\mid T}\mu(e)e\sum_i\sum_jij(\log iT+\log jT-\log d) \end{aligned}

只拿 \log iT 一项的求和出来说，剩下同理。

跟 e 有关的一项可以 \mathcal O(n\ln n) 预处理成为 F(T)：

\begin{aligned} &\sum_TTF(T)\sum_i\sum_jij\log iT\\ =&\sum_TTF(T)\sum_i\sum_jij(\log i+\log T)\\ =&\sum_TTF(T)\sum_ii(\sum_jj\log i+\sum_j j\log T)\\ =&\sum_TTF(T)(\sum_j j)(\sum_ii\log i+\log T\sum_ii)\\ \end{aligned}

然后这个式子就可以整除分块了，预处理 TF(T),i\log i,\log T 的前缀和即可。

时间复杂度 \mathcal O(mod+n\ln n+t\sqrt n)。

第二项可以 dirichlet 前缀和做到 \mathcal O(n\log\log n)，懒得写了。

#define mod 32465177
using mint = modint<mod-1>;
#define g 3
#define maxn 1001000
mint w[maxn];
int mu[maxn];
bool notprime[maxn];
int prime[maxn],cnt;
mint F[maxn],G[maxn],H[maxn],I[maxn],J[maxn];
void getprime(int n) {
    mu[1]=notprime[1]=1;
    for(int i=2; i<=n; ++i) {
        if(not notprime[i]) {
            prime[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1; j<=cnt&&prime[j]*i<=n; ++j) {
            notprime[i*prime[j]]=1;
            if(i%prime[j]==0) {
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
    rep(i,1,n)mu[i]*=i;
    rep(i,1,n)for(int j=i; j<=n; j+=i)F[j]+=mu[i],G[j]+=w[j/i]*mu[i];
    rep(i,1,n)F[i]*=i; 
    rep(i,1,n)H[i]=H[i-1]+G[i]*i,I[i]=I[i-1]+F[i],J[i]=J[i-1]+F[i]*w[i];
}
int n;
int arr[maxn<<1],m;
int gt(int n) {
    int l=1,r;
    while(l<=n) {
        r=n/(n/l);
        arr[m++]=l;
        arr[m++]=r+1;
        l=r+1;
    }
    return m;
}
mint W[maxn],Pre[maxn];
mint calc(int l,int r) {
    mint res=0;
    m=0;
    int p=gt(l),q=gt(r);
    inplace_merge(arr,arr+p,arr+q);
    m=unique(arr,arr+m)-arr;
    rep(i,0,m-2) {
        int p=arr[i],q=arr[i+1]-1;
        int L=l/p,R=r/q;
        res-=(H[q]-H[p-1])*(1ll*L*(L+1)/2)*(1ll*R*(R+1)/2);
    }
    auto wrk=[&](int l,int r)->mint {
        mint res=0;
        m=0;
        int p=gt(l),q=gt(r);
        inplace_merge(arr,arr+p,arr+q);
        m=unique(arr,arr+m)-arr;
        rep(i,0,m-2) {
            int p=arr[i],q=arr[i+1]-1;
            int L=l/p,R=r/q;
            res+=(mint)(1ll*R*(R+1)/2)*(Pre[L]*(I[q]-I[p-1])+(J[q]-J[p-1])*(1ll*L*(L+1)/2));
        }
        return res;
    };
    if(l!=r)res+=wrk(l,r)+wrk(r,l);
    else res+=wrk(l,r)*2;
    return res;
}
void solve() {
    int l,r;
    cin>>l>>r;
    cout<<qp(g,(calc(r,r)-calc(l-1,r)-calc(r,l-1)+calc(l-1,l-1)).val)<<'\n';
}
bool Med;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t>>n;
    for(int i=0,nw=1; i<mod-1; ++i,nw=1ll*nw*g%mod)if(nw<=n)w[nw]=i;
    rep(i,1,n)W[i]=W[i-1]+w[i];
    rep(i,1,n)Pre[i]=Pre[i-1]+w[i]*i; 
    getprime(n);
    while(t--)solve();
    return 0;
}

P7486 「Stoi2031」彩虹 题解

P7486 「Stoi2031」彩虹题解