题目描述
f(n) = GCD(1, n) + GCD(2, n) + GCD(3, n) + ~ ~ ~ + GCD(n - 1, n).
输入
每行一个整数N (1 < N < 4000000)，输入0的时候终止.
输出
对于输入的每一行输出要求的和.
样例输入
3176
17681
13080
0
样例输出
12684
17680
182220
我们假设gcd(n,i) = k，则gcd(n/k,i/k) = 1。即假设gcd(n/k, x ) = 1，则gcd(n,x*k) = k。gcd(n,i) = k,k的取值是确定的，即n的所有因子，所以，满足gcd(n/k,x) = 1个x的个数乘以k即为所有满足gcd(n,i) = k 的和。因此就转化为n/k的欧拉函数的值乘以k的所有的和。
举个例子12来说，12的因子为1，2，3，4，6，12，则和为12/1的欧拉函数值*1 + 12/2的欧拉函数值 * 2 + 12/3的欧拉函数值 * 3 + 12/4的欧拉函数值 * 4 + 12/6的欧拉函数值*6 + 12/12 的欧拉函数值 * 12。
我写的代码超时了... 无奈。
#include<cstdio>
#include<cmath>
int eular(int n)
{
int ret=,i;
for(i=;i*i<=n;i++){
if(n%i==){
n/=i,ret*=i-;
while(n%i==)
n/=i,ret*=i;
}
}
if(n>)
ret*=n-;
return ret;
}
long long a[];
int main()
{
int n; while(scanf("%d", &n) && n){
long long sum = , l = ;
//int p = sqrt(n * 1.0);
for(int i = ; i <= n; i++){
if(n % i == ){
a[++l] = i;
}
}
for(int i = ; i < l; i++){
long long m = n / a[i];
sum += eular(m) * a[i];
}
printf("%lld\n", sum);
}
return ;
}
这是学长的代码， 表示看不懂。。。
#include<stdio.h>
#include<string.h>
#define A 4000001
int p[A],ans[A];
int main()
{
int N,i,j;
memset(p,,sizeof(p));
memset(ans,,sizeof(ans));
p[]=;
for(i=;i<A;i++) //p[n]表示[1~n]与n互质的个数
if(!p[i])
for(j=i;j<A;j+=i)
{
if(!p[j]) p[j]=j;
p[j]=p[j]/i*(i-);
}
for(i=;i<A;i++) //求结果
for(j=i+i;j<A;j+=i)
ans[j]+=i*p[j/i];
while(scanf("%d",&N),N)
printf("%d\n",ans[N]);
}