G2. Hard Formula（困难版）题解

一、题目回顾（公式化描述）

给定 $n$，计算：

$$\boldsymbol{ \left( \sum_{k=1}^n \left( k \bmod \varphi(k) \right) \right) \bmod 2^{32} } $$

其中：

• $\varphi(k)$：欧拉函数，$1\sim k$ 中与 $k$ 互质的数的个数。
• 数据范围：$\boldsymbol{1 \le n \le 10^{12}}$
• 模数：$2^{32}$（unsigned int 自然溢出）

---

二、核心数学推导（解题基石）

1. 模运算恒等式

$$k \bmod \varphi(k) = k - \varphi(k) \cdot \left\lfloor \frac{k}{\varphi(k)} \right\rfloor $$

2. 求和式化简

$$\begin{aligned} \sum_{k=1}^n (k \bmod \varphi(k)) &= \sum_{k=1}^n k - \sum_{k=1}^n \varphi(k) \left\lfloor \frac{k}{\varphi(k)} \right\rfloor \\ &= \frac{n(n+1)}{2} - S \end{aligned} $$

最终答案公式：

$$\boldsymbol{ ans = \dfrac{n(n+1)}{2} - S }$$

其中 $S = \sum\limits_{k=1}^n \varphi(k) \left\lfloor \dfrac{k}{\varphi(k)} \right\rfloor$

---

三、关键数论性质（标程核心依据）

设 $g(k) = \left\lfloor \dfrac{k}{\varphi(k)} \right\rfloor$：

1. 质数幂 $p^e$：$\varphi(p^e)=p^e-p^{e-1} \implies g(k)=1$
2. 合数（多质因子）：$g(k) \ge 2$

结论：

• 只有质数幂贡献 $\varphi(k) \times 1$
• 其余数贡献 $\varphi(k) \times g(k)$

因此 $S$ 可拆分为：

$$S = \sum_{k \in \text{质数幂}} \varphi(k) + \sum_{k \notin \text{质数幂}} \varphi(k) \cdot g(k) $$

---

四、标程整体算法框架

标程采用 Min_25 筛 + 杜教筛 + 双层 DFS + 树状数组 顶级组合， 时间复杂度 $O(n^{2/3})$，可轻松处理 $n=10^{12}$。

算法流程

1. 线性筛预处理：预处理小范围欧拉函数 $\varphi$、质数表
2. DFS1 筛选：找出所有需要特殊计算的非质数幂数
3. Min_25/杜教筛：快速计算大范围欧拉函数前缀和
4. 贡献计算：分两段计算 $S$
   • 小质数：前缀和差分
   • 大质数：树状数组统计
5. 代入公式输出答案

---

五、标程代码逐模块深度解析

1. 全局定义与常数

typedef unsigned uint;
typedef unsigned long long ull;
const uint M=4e6+5, Pi=1e6+5, M2=5e8+5;
uint sum, F[M], G[M], pri[Pi], phi[M2], BIT[M];
ull N;

• $F, G$：欧拉函数前缀和（大/小范围）
• $phi$：线性筛欧拉函数
• $BIT$：树状数组，统计大质数贡献

---

2. 线性筛（欧拉函数+质数表）

void sieve(const uint&n){
    phi[1]=1;
    for(uint i=2;i<=n;++i){
        if(!phi[i]) pri[++top]=i, phi[i]=i-1;
        for(uint j=1;j<=top&&i*pri[j]<=n;++j){
            phi[i*pri[j]] = phi[i]*(pri[j]-1);
            if(i%pri[j]==0) { phi[i*pri[j]] += phi[i]; break; }
        }
    }
}

作用：

• 预处理 $\le n^{2/3}$ 范围的欧拉函数
• 生成质数表

---

3. 杜教筛（快速求欧拉前缀和）

void Getphi(const ull&n){
    // 初始化小区间 G
    for(uint i=1;i<=B;++i) G[i]=G[i-1]+phi[i];
    // 初始化大区间 F
    for(uint i=div(N,B);i>=1;--i) F[B]+=phi[i];
    // 杜教筛递归计算
    for(uint i=B2;i>=1;--i){
        ull T=div(N,i); uint lim=sqrt(T);
        F[i] = lim*G[lim] + T*(T-1)/2;
        for(uint k=2;k<=lim;++k){
            uint x=div(T,k);
            F[i] -= (i*k<=B?F[i*k]:G[x]) + phi[k]*x;
        }
    }
}

作用：

• 计算 $\sum_{i=1}^x \varphi(i)$
• 时间复杂度 $O(n^{2/3})$

---

4. DFS1（筛选非质数幂数）

bool DFS1(const ull&n,uint k,const ull&phi){
    ull T=div(N,n); uint w=int(n/phi)+1;
    uint R=pi[min(div(w*phi,w*phi-n), min(ull(B),T))];
    for(;k<=m;++k){
        uint p=pri[k]; if(p*p>T) break;
        if(k<=R) d[k].push_back(nb(n,phi));
        for(ull x=n,tp=phi*(p-1);x*p<=N;tp*=p)
            DFS1(x*=p,k+1,tp);
    }
    sum += phi*(Sp[R]-Sp[k-1]);
    return false;
}

作用：

• 递归枚举所有数
• 标记非质数幂，存入 d[i]
• 计算小质数直接贡献

---

5. 树状数组 + DFS2（大质数贡献）

for(uint i=m;i>lim;--i){
    uint p=pri[i];
    for(nb&x:d[i]){
        ull n=N/x.n/p, phi=x.phi*(p-1);
        while(n) sum+=phi*Qry(n), n/=p, phi*=p;
    }
    for(ull x=p,phi=p-1;x<=B;x*=p,phi*=p)
        DFS2(x,i+1,phi);
}

作用：

• 树状数组统计大质数幂贡献
• 避免重复计算，保证效率

---

6. 最终答案计算

uint Solve(const ull&n){
    // ... 预处理 ...
    return n*(n+1)/2 - sum;
}

严格对应公式：

$$ans = \frac{n(n+1)}{2} - S$$

---

六、样例验证（$n=5$）

$$\begin{aligned} &1\bmod 1=0,\ 2\bmod 1=0,\ 3\bmod 2=1,\\ &4\bmod 2=0,\ 5\bmod 4=1 \end{aligned} $$

求和：$0+0+1+0+1=2$ 标程输出：$\boldsymbol{2}$ ✔️

---

七、复杂度与正确性

• 时间：$O(n^{2/3}) \approx 10^8$，10秒时限完全通过
• 空间：$O(n^{2/3})$，1GB内存充足
• 模数：unsigned int 自然溢出 $\equiv \bmod 2^{32}$
• 范围：完美支持 $n \le 10^{12}$（G2 困难版）

---

八、总结（最简核心）

1. 公式化简：$k \bmod \varphi(k) = k - \varphi(k)\lfloor k/\varphi(k) \rfloor$
2. 答案：$\boldsymbol{ans = \dfrac{n(n+1)}{2} - \sum \varphi(k)\lfloor k/\varphi(k) \rfloor}$
3. 算法：杜教筛 + 双层DFS + 树状数组
4. 适用：$n \le 10^{12}$ 顶级数论求和