给定一个整数N，请你求出gcd(1,N)+gcd(2,N)+gcd(3,n)...+gcd(N,N)d N,N)的值。 1<=n<=2的31次方-1 样例输入 复制 6 样例输出 复制 15 来源/分类 数论 欧拉函数
已知： \[ S(N) = \sum_{k=1}^N \gcd(k, N) \] 要求 \(1 \le N \le 2^{31}-1\)。 --- ## 1. 推导公式 设 \(d\) 是 \(N\) 的约数，即 \(d \mid N\)。 \(\gcd(k, N) = d\) 当且仅当 \(\gcd\left(\frac{k}{d}, \frac{N}{d}\right) = 1\)，且 \(1 \le k \le N\)。 满足条件的 \(k\) 的个数为 \(\varphi\left(\frac{N}{d}\right)\)，其中 \(\varphi\) 是欧拉函数。 因此： \[ \sum_{k=1}^N \gcd(k, N) = \sum_{d \mid N} d \cdot \varphi\left(\frac{N}{d}\right) \] 或者等价地（令 \(d' = \frac{N}{d}\)）： \[ \sum_{d \mid N} \varphi(d) \cdot \frac{N}{d} \] --- ## 2. 更简洁的形式 已知数论恒等式： \[ \sum_{k=1}^N \gcd(k, N) = \sum_{d \mid N} d \cdot \varphi\left(\frac{N}{d}\right) \] 也可以写成： \[ \sum_{d \mid N} \varphi(d) \cdot \frac{N}{d} \] 但更常用的是： \[ \sum_{d \mid N} d \cdot \varphi\left(\frac{N}{d}\right) \] 因为计算时枚举 \(N\) 的约数 \(d\)，直接求 \(\varphi(N/d)\) 即可。 --- ## 3. 算法步骤 1. 对 \(N\) 分解质因数。 2. 枚举 \(N\) 的所有约数 \(d\)（通过质因数组合）。 3. 对每个 \(d\)，计算 \(\varphi\left(\frac{N}{d}\right)\)。 4. 累加 \(d \cdot \varphi\left(\frac{N}{d}\right)\)。 --- ## 4. 时间复杂度 \(N\) 最多约 \(2.1 \times 10^9\)，约数个数最多约 \(1536\) 个（实际更少）。 分解质因数用试除到 \(\sqrt{N}\) 即可（\(\sqrt{N} \approx 46340\)），可以接受。 枚举约数并计算欧拉函数是可行的。 --- ## 5. 代码实现（C++） ```cpp #include <iostream> #include <vector> #include <cmath> using namespace std; // 分解质因数 vector<pair<long long, int>> factorize(long long n) { vector<pair<long long, int>> factors; for (long long p = 2; p * p <= n; p++) { if (n % p == 0) { int cnt = 0; while (n % p == 0) { n /= p; cnt++; } factors.emplace_back(p, cnt); } } if (n > 1) { factors.emplace_back(n, 1); } return factors; } // 通过质因数计算欧拉函数 long long euler_phi(long long n, const vector<pair<long long, int>>& factors) { long long res = n; for (auto& [p, _] : factors) { if (n % p == 0) { res -= res / p; } } return res; } // 生成所有约数 void generate_divisors(int idx, long long cur, const vector<pair<long long, int>>& factors, vector<long long>& divisors) { if (idx == factors.size()) { divisors.push_back(cur); return; } long long p = factors[idx].first; int exp = factors[idx].second; long long pow = 1; for (int i = 0; i <= exp; i++) { generate_divisors(idx + 1, cur * pow, factors, divisors); pow *= p; } } int main() { long long N; cin >> N; // 分解 N 的质因数 auto factors = factorize(N); // 生成 N 的所有约数 vector<long long> divisors; generate_divisors(0, 1, factors, divisors); // 计算 S(N) = sum_{d|N} d * phi(N/d) long long ans = 0; for (long long d : divisors) { long long m = N / d; // 计算 phi(m)，需要 m 的质因数分解 // 但 m 的质因数一定是 N 的质因数的子集 // 所以可以从 factors 中筛选出整除 m 的质因数 vector<pair<long long, int>> m_factors; long long tmp = m; for (auto& [p, exp] : factors) { if (tmp % p == 0) { int cnt = 0; while (tmp % p == 0) { tmp /= p; cnt++; } m_factors.emplace_back(p, cnt); } } if (tmp > 1) { m_factors.emplace_back(tmp, 1); } long long phi_m = euler_phi(m, m_factors); ans += d * phi_m; } cout << ans << endl; return 0; } ``` --- ## 6. 样例验证 输入： ``` 6 ``` 约数：1, 2, 3, 6 计算： - d=1, N/d=6, φ(6)=2 → 贡献 1×2=2 - d=2, N/d=3, φ(3)=2 → 贡献 2×2=4 - d=3, N/d=2, φ(2)=1 → 贡献 3×1=3 - d=6, N/d=1, φ(1)=1 → 贡献 6×1=6 总和：2+4+3+6=15 ✅ --- 最终公式： \[ S(N) = \sum_{d \mid N} d \cdot \varphi\left(\frac{N}{d}\right) \] 用上述代码可在 \(O(\sqrt{N} + \tau(N)^2)\) 时间内完成，其中 \(\tau(N)\) 是 \(N\) 的约数个数。 [2026-01-20 14:05:17 | AI问答 | 1434点数解答]
- [DeepSeek] 给定一个整数N，请你求出gcd(1,N)+gcd(2,N)+gcd(3,n)...+gcd(N,N)d N,N)的值。 1<=n<=2的31次方-1 样例输入 复制 6 样例输出 复制 15 来源/分类 数论 欧拉函数（1434点数解答 | 2026-01-20 14:05:17）17
- [字节豆包] 题目描述 给定一个包含 n n 个整数的数列，请统计其中有多少个整数满足大于 x x 且小于 y y，并输出所有满足要求的整数之和 例如： n n = 6 6，数列为 [ 13 ， 31 ， 45 ， 17 ， 20 ， 99 ] [13，31，45，17，20，99]； x = 18 x=18， y = 50 y=50，数列中满足大于 18 18 且小于 50 50 的整数有 31 、 45 、 20 31、45、20，和为 96 （ 31 + 45 + 20 ） 96（31+45+20）。 输入格式 第一行输入三个整数 n n、 x x 和 y y，整数之间以一个空格隔开； 第二行输入 n n 个整数，整数之间以一个空格隔开。 输出格式 输出一个整数，表示数列中所有满足大于 x x 且小于 y y 的整数之和。 input1 复制 6 18 50 13 31 45 17 20 99 output1 复制 96 数据规模与约定 1 ≤ n ≤ 1000 1≤n≤1000， 1 ≤ x ＜ y ≤ 5000 1≤x＜y≤5000, 1 ≤ 1≤ 每个（281点数解答 | 2025-11-29 20:20:58）94
- [讯飞星火] import math def gcd(a, b): if a == 0 or b == 0: return 0 return math.gcd(a, b) def lcm(a, b): return abs(a * b) // gcd(a, b) num1 = eval(input("请输入正整数a：")) num2 = eval(input("请输入正整数b：")) print("最大公约数:", gcd(num1, num2)) print("最小公倍数:", lcm(num1, num2))（457点数解答 | 2024-11-25 18:17:48）365
- [字节豆包] #include <stdio.h> struct DateG { int yy, mm, dd; }; // 判断是否为闰年 char leapYear(int year) { return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0); } // 每个月的天数 int monthDays[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; // 计算自公元1年1月1日到指定的日期共经历了多少天 int Days(struct DateG x) { int days = 0; // 计算之前年份的总天数 for (int year = 1; year < x.yy; year++) { days += 365 + leapYear(year); } // 计算当前年份到当前月份之前的总天数 for (int month = 1; month < x.mm; month++（1504点数解答 | 2025-12-12 20:54:15）36
- [DeepSeek] 给定一个包含 n n 个整数的数列，请统计其中有多少个整数满足大于 x x 且小于 y y，并输出所有满足要求的整数之和 例如： n n = 6 6，数列为 [ 13 ， 31 ， 45 ， 17 ， 20 ， 99 ] [13，31，45，17，20，99]； x = 18 x=18， y = 50 y=50，数列中满足大于 18 18 且小于 50 50 的整数有 31 、 45 、 20 31、45、20，和为 96 （ 31 + 45 + 20 ） 96（31+45+20）。 输入格式 第一行输入三个整数 n n、 x x 和 y y，整数之间以一个空格隔开； 第二行输入 n n 个整数，整数之间以一个空格隔开。 输出格式 输出一个整数，表示数列中所有满足大于 x x 且小于 y y 的整数之和。c++ （168点数解答 | 2025-11-14 16:47:26）76
- [DeepSeek] 给定一个包含 n n 个整数的数列，请统计其中有多少个整数满足大于 x x 且小于 y y，并输出所有满足要求的整数之和 例如： n n = 6 6，数列为 [ 13 ， 31 ， 45 ， 17 ， 20 ， 99 ] [13，31，45，17，20，99]； x = 18 x=18， y = 50 y=50，数列中满足大于 18 18 且小于 50 50 的整数有 31 、 45 、 20 31、45、20，和为 96 （ 31 + 45 + 20 ） 96（31+45+20）。 输入格式 第一行输入三个整数 n n、 x x 和 y y，整数之间以一个空格隔开； 第二行输入 n n 个整数，整数之间以一个空格隔开。 输出格式 输出一个整数，表示数列中所有满足大于 x x 且小于 y y 的整数之和。 使用c++语言（101点数解答 | 2026-01-18 19:03:32）25
- [字节豆包] # 【mx-x5-t2】「gfoi round 1」interstellar ## 题目背景 > [interstellar - pikasonic](https://music.163.com/#/song?id=1900207101) ## 题目描述 你有一个正整数 $x$，你可以对它进行如下操作： - 选择一个正整数 $y$，把 $x$ 变为它的 $\gcd(x, y)$ 倍，即 $x \gets x \times \gcd(x, y)$。 （$\gcd(x, y)$ 表示 $x, y$ 的最大公因数。） $x$ 的初始值为 $n$，你想通过若干次操作（也可不操作）将它变为 $m$。你想知道至少要多少次操作才能达成目标，或报告无解。 ## 输入格式 **本题有多组测试数据。** 第一行输入一个正整数 $t$，表示测试数据组数。 对于每组测试数据： 第一行包含两个正整数 $n, m$。 ## 输出格式 对于每组数据： - 若无解，即 $x$ 无论如何操作都不能变成 $m$，输出 $-1$。 - 否则输出一行一个非负整数，表示最小的操作次数。 ##（256点数解答 | 2024-09-28 15:36:37）158
- [字节豆包] c++ # 【mx-x5-t2】「gfoi round 1」interstellar ## 题目背景 > [interstellar - pikasonic](https://music.163.com/#/song?id=1900207101) ## 题目描述 你有一个正整数 $x$，你可以对它进行如下操作： - 选择一个正整数 $y$，把 $x$ 变为它的 $\gcd(x, y)$ 倍，即 $x \gets x \times \gcd(x, y)$。 （$\gcd(x, y)$ 表示 $x, y$ 的最大公因数。） $x$ 的初始值为 $n$，你想通过若干次操作（也可不操作）将它变为 $m$。你想知道至少要多少次操作才能达成目标，或报告无解。 ## 输入格式 **本题有多组测试数据。** 第一行输入一个正整数 $t$，表示测试数据组数。 对于每组测试数据： 第一行包含两个正整数 $n, m$。 ## 输出格式 对于每组数据： - 若无解，即 $x$ 无论如何操作都不能变成 $m$，输出 $-1$。 - 否则输出一行一个非负整数，表示最小的操作次数。（293点数解答 | 2024-09-28 15:37:18）244
- [字节豆包] 给定一个包含 个元素的**整数**序列 ，记作 。 求另一个包含 个元素的待定**整数**序列 ，记 ，使得 且 尽可能的小。 输入 第一行一个整数 ，表示序列元素个数。 第二行 个整数，表示序列 。 输出 一行一个整数，表示 的前提下 的最小值。 样例输入 复制 2 4059 -1782 样例输出 复制 99 提示 对于 的数据， ， ，且 序列不全为 来源/分类（746点数解答 | 2026-01-24 13:14:40）29
- [字节豆包] 请编写函数，求两个自然数的最大公约数。 函数原型 long long Gcd(long long x, long long y); 说明：参数 x、y 为自然数。函数值为它们的最大公约数。若 x、y 都为 0，则函数值规定为 1。 裁判程序 #include <stdio.h> long long Gcd(long long x, long long y); int main() { long long a, b; scanf("%lld %lld", &a, &b); printf("%lld\n", Gcd(a, b)); return 0; } /* 你提交的代码将被嵌在这里 */ 要求：用递归方法完成函数的设计，不得使用循环语句。 输入样例1 21 30 输出样例1 3 输入样例2 39 28 输出样例2 1 （73点数解答 | 2025-12-25 14:49:12）37
- [字节豆包] 给你一个正整数 ，输出A的最高位的比特与最低位的比特。 例如，给你 A=26，我们可以将A化成二进制为 11010 则A 的最高数是 10000，输出 10000 的十进制为 16。 则A 的最低数是 10，输出 10 的十进制为 2。 再例如，给你 A=88，我们可以将A化成二进制为 1011000 则A的最高数是1000000，输出为64。 则A的最低数是1000，输出为8。 输入 每行输入一个正整数 。 输出 输出对应的最高数，最低数，一行一个。 样例输入 复制 88 样例输出 复制 64 8 来源/分类 数论 位运算（398点数解答 | 2026-01-23 19:47:50）28
- [字节豆包] 计算 和 的最大公约数和最小公倍数。 输入 两个整数表示 和 ， 样例输入 复制 10 15 样例输出 复制 5 30 来源/分类 数论 最大公约数 回答篇幅：简单明了（164点数解答 | 2026-01-24 13:05:12）22