| 题目名称 | 931. [河南省队2012] 最大公约数和 |
|---|---|
| 输入输出 | gcdsum.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 wo shi 刘畅
于2012-07-17加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：168， 提交：479， 通过率：35.07% | ||||
 诺亚 |
100 | 0.000 s | 0.00 MiB | C++ |
 浮生随想 |
100 | 0.000 s | 0.00 MiB | C++ |
 沉迷学习的假的Keller |
100 | 0.000 s | 0.00 MiB | C++ |
 APWTMECRD |
100 | 0.000 s | 0.00 MiB | C++ |
 烟雨 |
100 | 0.000 s | 0.00 MiB | C++ |
 数声风笛ovo |
100 | 0.000 s | 0.00 MiB | C++ |
 Sky_miner |
100 | 0.001 s | 0.26 MiB | C++ |
 赵赵赵 |
100 | 0.002 s | 0.18 MiB | Pascal |
 xl |
100 | 0.002 s | 0.31 MiB | C++ |
 wo shi 刘畅 |
100 | 0.003 s | 0.17 MiB | Pascal |
| 本题关联比赛 | |||
| 20120718 | |||
| 矩阵乘法练习赛 | |||
| 关于 最大公约数和 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
手抖，乘号变除号。。。。
 再见
2017-01-20 16:37
9楼
| ||||
|
51nod.......
 YGOI_真神名曰驴蛋蛋
2017-01-02 05:53
8楼
| ||||
|
O(sqrt(n)*log(n))新算法
| ||||
|
给你n,然后求[1-n]所有数与n的最大公约数的和
n的最大公约数必定是n的因子v，所以考虑枚举因子分别求他们的个数num，那么因子v对答案的贡献就是v*num 相当于求[1-n]中 GCD(a[i],n) = v的个数,也就成了GCD(a[i]/v,n/v)=1的个数。 欧拉函数求出即可。 欧拉函数：[1-n]中 gcd[i,n]=x的个数  安呐一条小咸鱼。
2016-10-03 19:39
6楼
| ||||
|
这时限，mdzz......
 AntiLeaf
2016-09-18 17:26
5楼
| ||||
|
谁能证明复杂度上界。。。。。。
| ||||
|
怎么时限还是0.01s
 Dissolute丶Tokgo
2015-10-14 07:52
3楼
| ||||
|
特么才知道欧拉函数的含义是这个意思。。。我特么居然傻叉的打了个莫比乌斯函数来求欧拉函数。。。。。
 C语言入门
2014-01-07 21:23
2楼
| ||||
|
似乎需要用欧拉函数，后来看看，表示不会了
| ||||
Hzoi_Go灬Fire
神利·代目
Truth.Cirno【题目描述】
给定一个整数$N$，你需要求出$$\sum\limits_{i=1}^{N}\gcd(i,N)$$。
【输入格式】
一个整数，为N。
【输出格式】
一个整数，为所求的答案。
【样例输入】
6
【样例输出】
15
【数据范围】
对于30%的数据，$n\leq 1024$；
对于60%的数据，$n\leq 10^6$；
对于80%的数据，$n\leq 10^7$；
对于100%的数据，$n\leq 2^{31}-1$。