|
手抖，乘号变除号。。。。
题目 931 [河南省队2012] 最大公约数和
2017-01-20 16:37:04
|
|
51nod.......
题目 931 [河南省队2012] 最大公约数和
2017-01-02 05:53:47
|
|
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的个数
题目 931 [河南省队2012] 最大公约数和
2016-10-03 19:39:17
|
|
这时限，mdzz......
题目 931 [河南省队2012] 最大公约数和
2016-09-18 17:26:31
|
|
谁能证明复杂度上界。。。。。。
|
|
怎么时限还是0.01s
题目 931 [河南省队2012] 最大公约数和
2015-10-14 07:52:22
|
|
特么才知道欧拉函数的含义是这个意思。。。我特么居然傻叉的打了个莫比乌斯函数来求欧拉函数。。。。。
题目 931 [河南省队2012] 最大公约数和
2014-01-07 21:23:01
|
|
似乎需要用欧拉函数，后来看看，表示不会了
|