G1. Hard Formula 题解

一、题目翻译与公式整理

题目描述

这是本题的简单版本，两个版本的区别仅在于 $n$ 的范围与时间限制不同。

给定一个整数 $n$，计算：

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

其中 $\varphi(k)$ 是欧拉函数，表示 $1 \sim k$ 中与 $k$ 互质的数的个数。

数据范围

$1 \le n \le 10^{10}$

---

二、核心数学公式推导（解题关键）

1. 模运算化简

根据模运算定义：

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

对求和式变形：

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

2. 最终答案公式

$$\boldsymbol{ans} = \frac{n(n+1)}{2} - 1 - \sum_{k=2}^n \varphi(k) \cdot \left\lfloor \frac{k}{\varphi(k)} \right\rfloor $$

• 前半部分：$1\sim n$ 求和 $\dfrac{n(n+1)}{2}$
• 后半部分：标程用杜教筛 + 数论分块 + DFS 快速计算

---

三、核心性质：$\boldsymbol{\left\lfloor \dfrac{k}{\varphi(k)} \right\rfloor}$

这是整个算法的灵魂：

1. 质数：$\varphi(p)=p-1 \implies \left\lfloor \dfrac{p}{p-1} \right\rfloor = 1$
2. 质数幂 $p^e$：$\varphi(p^e)=p^e-p^{e-1} \implies \left\lfloor \dfrac{p^e}{\varphi(p^e)} \right\rfloor = \left\lfloor \dfrac{p}{p-1} \right\rfloor = 1$
3. 合数且有至少两个不同质因子：$\left\lfloor \dfrac{k}{\varphi(k)} \right\rfloor = g$（常数，$g\ge2$）

结论：

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

---

四、标程算法框架

标程使用 Min_25 筛思想 + 杜教筛 + 记忆化 DFS，在 $O(n^{2/3})$ 时间内求解 $10^{10}$ 范围。

整体流程

1. 预处理小范围欧拉函数前缀和
2. Min_25 筛计算质数前缀和
3. DFS 递归计算 $\sum \varphi(k) \cdot \lfloor k/\varphi(k) \rfloor$
4. 代入公式得到答案

---

五、标程代码逐段详细解析

1. 全局定义

typedef unsigned long long ull;
typedef unsigned uint;
const uint M=1e6+5;
ull N; const uint ANS[11]={0,0,0,1,1,2,2,3,3,6,8}; // 小数据打表
uint B,n4,top,pri[M];
uint F0[M],F1[M],G0[M],G1[M]; // Min_25 筛数组
uint SF[M],SG[M];             // 欧拉函数前缀和

• $B = \sqrt{N}$：数论分块边界
• $F0,F1$：大区间前缀和
• $G0,G1$：小区间前缀和
• $SF[i] = \sum\varphi(x)$（$x\le N/i$）

---

2. Min_25 筛（核心：求欧拉函数前缀和）

for(uint p=2;p<=n4;++p)if(G0[p]!=G0[p-1]){
    const uint&lim=Div(B,p),&S0=G0[p-1],&S1=G1[p-1];
    pri[++top]=p;
    // 更新大区间
    for(uint k=1;k<=lim;++k){
        F0[k]-=F0[k*p]-S0;
        F1[k]-=p*(F1[k*p]-S1);
    }
    // 更新小区间
    for(uint k=B;k>=p*p;--k){
        G0[k]-=G0[k/p]-S0;
        G1[k]-=p*(G1[k/p]-S1);
    }
}

作用：

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

---

3. DFS 递归计算贡献（标程核心）

inline uint DFS(const ull&n,uint k,const ull&phi){
    const ull&T=Div(N,n);
    const uint&g=int(n*1./phi);
    const ull&R=min((g+1)*phi*phi/((g+1)*phi-n), min(ull(B),T));
    uint ans=0;
    // 边界：无质数可选
    if(k>top)ans=T<=B?0:g*phi*(SF[n]-SG[B]);
    // 递归枚举质因子
    for(;k<=top;++k){
        const uint&p=pri[k],&w=p<=R?g+1:g;
        if(1ull*p*p>T)break;
        // 枚举质数幂 p^e
        for(ull x=n,tp=phi*(p-1);x*p<=N;tp*=p)
            ans+=DFS(x*=p,k+1,tp)+w*tp;
        ans-=w*phi*(p-1);
    }
    return ans;
}

功能：

• 枚举所有数的质因子分解
• 按质数幂 / 合数分类计算贡献
• 自动合并相同值，大幅加速

---

4. 主函数：最终答案计算

scanf("%llu",&N);
if(N<=10)return!printf("%d",ANS[N]);
B=sqrt(N);n4=sqrt(B);
// Min_25 筛预处理...
// 计算 SF = sum phi(x)
for(uint i=1;i<=B;++i)SF[i]=F1[i]-F0[i],SG[i]=G1[i]-G0[i];
// 最终公式
printf("%u",N*(N+1)/2-1-DFS(1,1,1));

最终公式：

$$ans = \frac{N(N+1)}{2} - 1 - DFS(1,1,1)$$

完美对应我们推导的数学式。

---

六、样例验证（$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$，与样例输出一致。

---

七、复杂度与正确性

• 时间复杂度：$O(N^{2/3}) \approx 10^6$ 次计算，$2$ 秒轻松通过
• 空间复杂度：$O(\sqrt{N})$，远低于 1GB 限制
• 模数：使用 unsigned int 自然溢出，等价于 $\bmod 2^{32}$

---

八、题解总结

1. 公式化简：$k \bmod \varphi(k) = k - \varphi(k)\lfloor k/\varphi(k) \rfloor$
2. 高效求解：用 Min_25 筛 + DFS 计算大数范围欧拉函数贡献
3. 答案计算：$ans = \dfrac{n(n+1)}{2} - 1 - DFS(1,1,1)$