题目分析

题目要求计算 (n) 重求和 (\sum_{i_1=1}^{m}\sum_{i_2=1}^{m} \dots \sum_{i_n=1}^{m}\gcd(i_1,i_2,\dots,i_n))，其中 (n,m) 可达 (10^{11})。直接枚举显然不可行，需通过数论变换（莫比乌斯反演或欧拉函数）结合整除分块、杜教筛优化求解。

解题思路

1. 数论变换：利用 (\gcd(i_1,\dots,i_n) = \sum_{d|i_1,\dots,d|i_n} \phi(d))（欧拉函数的性质），将求和转化为对 (d) 的枚举： [ \sum_{d=1}^m \phi(d) \cdot \left\lfloor \frac{m}{d} \right\rfloor^n ]
2. 预处理与杜教筛：预处理小范围欧拉函数前缀和，大范围使用杜教筛递归计算。
3. 整除分块：对 (\left\lfloor \frac{m}{d} \right\rfloor) 相同的 (d) 分块，减少计算量。
4. 快速幂：计算 (\left\lfloor \frac{m}{d} \right\rfloor^n) 时使用快速幂，时间复杂度 (O(\log n))。

代码实现（带注释）

#include <bits/stdc++.h>
#define int unsigned long long  // 使用unsigned long long避免溢出
using namespace std;

const int M = 1e7;  // 预处理欧拉函数的上限
unordered_map <int, int> mp;  // 杜教筛用的哈希表，存储已计算的前缀和
int phi[M + 10], pri[M], c = 0;  // phi数组存储欧拉函数值，pri存储质数，c是质数计数
bitset < M + 10 > is;  // 筛法用的布尔数组，标记是否为合数

// 快速幂：计算a^k，对2^64取模（自然溢出）
int Pow(int a, int k) {
    int ans = 1;
    for (; k; k >>= 1, a = a * a)  // 二进制分解指数k
        if (k & 1)
            ans = ans * a;
    return ans;
}

// 预处理欧拉函数及前缀和（埃氏筛+线性筛）
void init() {
    phi[1] = 1;  // 1的欧拉函数值为1
    for (int i = 2; i <= M; i++) {
        if (!is[i]) {  // i是质数
            pri[++c] = i;
            phi[i] = i - 1;  // 质数的欧拉函数值为自身减一
        }
        for (int j = 1; j <= c && pri[j]*i <= M; j++) {
            is[i * pri[j]] = 1;  // 标记为合数
            if (i % pri[j] == 0) {  // pri[j]是i的质因子
                phi[i * pri[j]] = phi[i] * pri[j];  // 欧拉函数性质
                break;
            }
            phi[i * pri[j]] = phi[i] * phi[pri[j]];  // 互质时欧拉函数乘积
        }
    }
    // 计算欧拉函数前缀和
    for (int i = 2; i <= M; i++)
        phi[i] += phi[i - 1];
}

// 杜教筛：计算欧拉函数前缀和sum_{i=1}^n phi(i)
int sum_phi(int n) {
    if (n <= M)  // 小范围直接返回预处理结果
        return phi[n];
    if (mp.count(n))  // 已计算过，直接返回哈希表中的值
        return mp[n];
    
    // 初始值：sum_{i=1}^n i = n*(n+1)/2
    int ans;
    if (n & 1)
        ans = (n + 1) / 2 * n;
    else
        ans = n / 2 * (n + 1);
    
    // 整除分块递归计算
    for (int l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);  // 相同n/l的右端点
        ans -= (r - l + 1) * sum_phi(n / l);  // 减去多余部分
    }
    
    return mp[n] = ans;  // 存入哈希表并返回
}

int n, k, ans = 0;  // n是重数，k是m，ans存储最终答案

signed main() {
    ios::sync_with_stdio(0);  // 加速输入输出
    cin.tie(0), cout.tie(0);
    init();  // 预处理欧拉函数
    cin >> n >> k;
    
    // 整除分块计算答案
    for (int l = 1, r; l <= k; l = r + 1) {
        r = k / (k / l);  // 相同k/l的右端点
        // 累加 phi[r]-phi[l-1] 乘以 (k/l)^n
        ans = (ans + (sum_phi(r) - sum_phi(l - 1)) * Pow(k / l, n));
    }
    
    cout << ans;  // 输出答案（自然溢出即为对2^64取模）
    return 0;
}

代码解释

1. 预处理欧拉函数：使用线性筛法预处理 (1) 到 (10^7) 的欧拉函数值及前缀和，时间复杂度 (O(M))。
2. 杜教筛：递归计算大范围欧拉函数前缀和，通过整除分块减少递归次数，时间复杂度 (O(n^{2/3}))。
3. 整除分块：对 (d) 按 (\left\lfloor \frac{m}{d} \right\rfloor) 分块，每块内的 (\left\lfloor \frac{m}{d} \right\rfloor^n) 相同，结合快速幂计算，时间复杂度 (O(\sqrt{m} \log n))。
4. 自然溢出：利用 unsigned long long 的自然溢出特性实现对 (2^{64}) 取模，无需额外取模操作。