首页 > 代码库 > 1188 最大公约数之和 V2
1188 最大公约数之和 V2
1188 最大公约数之和 V2
题目来源： UVA
基准时间限制：2 秒 空间限制：262144 KB
给出一个数N，输出小于等于N的所有数，两两之间的最大公约数之和。
相当于计算这段程序（程序中的gcd(i,j)表示i与j的最大公约数）：
G=0;
for(i=1;i<N;i++)
for(j=i+1;j<=N;j++)
{
G+=gcd(i,j);
}
Input
第1行：1个数T，表示后面用作输入测试的数的数量。(1 <= T <= 50000)第2 - T + 1行：每行一个数N。(2 <= N <= 5000000)
Output
共T行，输出最大公约数之和。
Input示例
310100200000
Output示例
6713015143295493160
思路：欧拉函数；
http://www.cnblogs.com/zzuli2sjy/p/5831575.html是这个题的加强版，这里用筛法求欧拉函数，然后再用类似筛法的方法求每个数的约数对答案的贡献，最后求下前缀和
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<queue> 6 #include<math.h> 7 #include<set> 8 #include<vector> 9 #include<string.h>10 using namespace std;11 typedef long long LL;12 bool prime[5000005];13 int oula[5000005];14 int ans[5000005];15 LL ask[5000005];16 int main(void)17 {18 int i,j;19 int T,N;20 for(i = 2; i <= 3000; i++)21 {22 if(!prime[i])23 {24 for(j = i; (i*j)<=5000005; j++)25 {26 prime[i*j]=true;27 }28 }29 }30 int cn = 0;31 for(i = 2; i <= 5000000; i++)32 {33 if(!prime[i])34 {35 ans[cn++]=i;36 }37 }38 for(i = 0; i <= 5000000 ; i++)39 oula[i]=i;40 oula[1]=0;41 memset(ask,0,sizeof(ask));42 for(i = 0; i < cn; i++)43 {44 for(j = 1; j*ans[i] <= 5000000 ; j++)45 {46 oula[j*ans[i]]/=ans[i];47 oula[j*ans[i]]*=ans[i]-1;48 }49 }50 for(i = 1; i <= 5000000; i++)51 {52 for(j = 2; (i*j) <= 5000000; j++)53 {54 ask[i*j]+=oula[j]*i;55 }56 }57 for(i = 2;i <= 5000000; i++)58 {59 ask[i]+=ask[i-1];60 }61 scanf("%d",&T);62 while(T--)63 {64 scanf("%d",&N);65 printf("%lld\n",ask[N]);66 }67 return 0;68 }
1188 最大公约数之和 V2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。