题解归档 - cf915G

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf915G
• 本地来源：problems/cf915G/idea.md
• 题目链接：https://codeforces.com/contest/915/problem/G
• 原始标题：CF915G Coprime Arrays

思路

CF915G Coprime Arrays

题意

给定 n, k。对每个 i ∈ [1,k]，统计长度为 n、每个元素在 [1,i] 且全体 gcd = 1 的数组个数 b_i（模 10^9+7）。

输出：Σ_{i=1}^{k} (b_i ⊕ i) mod 10^9+7（注意不是所有 b_i 的 XOR；样例 3 4 → 82）。

做法

计数公式（莫比乌斯反演）

全体数组 i^n 个。所有元素均为 d 的倍数的数组有 ⌊i/d⌋^n 个，故

[
b_i = \sum_{d=1}^{i} \mu(d)\cdot \lfloor i/d \rfloor^n
]

增量维护（O(k log k)）

令 f(m) = b_m。当 m 增大到 m 时，只有 d | m 时 ⌊m/d⌋ 才会 +1：

[
f(m) = f(m-1) + \sum_{d|m} \mu(d)\cdot\big(\lfloor m/d \rfloor^n - (\lfloor m/d \rfloor - 1)^n\big)
]

预处理 μ[1..k]（线性筛）与 pw[j]=j^n mod MOD，枚举 m=1..k 的因子更新 b_m，累加 (b_m ⊕ m)。

复杂度 O(k log k)，空间 O(k)。

验证

• 样例 3 4 → 82；2000000 8 → 339310063
• 对拍：brute 直接按公式双重循环（小 k）

代码

来源：problems/cf915G/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:44:55
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2000005,mod=1000000007;
bool not_prime[maxn+5];
ll p[maxn/10+5],mu[maxn+5],pw[maxn+5],df[maxn+5],ptot;
ll qmksm(ll a,ll b){
    ll sc=1,zc=a%mod;
    while(b){
        if(b&1) sc=sc*zc%mod;
        b>>=1,zc=zc*zc%mod;
    }
    return sc;
}
void mu_sieve(ll n){
    ll i,j;
    mu[1]=1;
    for(i=2;i<=n;i++){
        if(not_prime[i]==0) p[++ptot]=i,mu[i]=-1;
        for(j=1;j<=ptotandi*p[j]<=n;j++){
            not_prime[i*p[j]]=1;
            if(i%p[j]==0){
                mu[i*p[j]]=0;
                break;
            }
            mu[i*p[j]]=-mu[i];
        }
    }
}
int main(){
    ll n,k,i,j,d,v,l,r,zc,pd,cur,dq,cnt,ans;
    cin>>n>>k;
    mu_sieve(k);
    for(i=0;i<=k;i++) pw[i]=qmksm(i,n);
    for(d=1;d<=k;d++){
        if(mu[d]==0) continue;
        zc=(mu[d]%mod+mod)%mod;
        for(v=1;v<=k/d;v++){
            l=v*d,r=min((v+1)*d-1,k);
            pd=zc*pw[v]%mod;
            df[l]=(df[l]+pd)%mod;
            df[r+1]=(df[r+1]-pd+mod)%mod;
        }
    }
    cur=0,ans=0;
    for(i=1;i<=k;i++){
        cur=(cur+df[i])%mod;
        ans=(ans+(cur^i))%mod;
    }
    cout<<ans<<"\n";
    return 0;
}