首页 > 代码库 > 1363 最小公倍数之和
1363 最小公倍数之和
1363 最小公倍数之和
题目来源： SPOJ
基准时间限制：1.5 秒 空间限制：131072 KB
给出一个n，求1-n这n个数，同n的最小公倍数的和。
例如：n = 6，1,2,3,4,5,6 同6的最小公倍数分别为6,6,6,12,30,6，加在一起 = 66。
例如：n = 6，1,2,3,4,5,6 同6的最小公倍数分别为6,6,6,12,30,6，加在一起 = 66。
由于结果很大，输出Mod 1000000007的结果。
Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 50000)第2 - T + 1行：T个数A[i](A[i] <= 10^9)
Output
共T行，输出对应的最小公倍数之和
Input示例
3569
Output示例
5566279
思路：欧拉函数；
最小公倍数可以表示为n*m/gcd(n,m);那么要求的就可以写为sum（i，N）= N*sum（i/gcd(N,i)）;我们把式子再化下就是(N/gcd(N,i))*gcd(N,i)*sum(i/gcd(N,i));
那么后面i/gcd(N,i)是与N/gcd(N,i)互质的数，那么当那么sum（i/gcd（N,i））,就是oula（N/gcd(N,i)）*(N/gcd(N,i))/2;N/gcd(N,i)为N的约数，所以只要求所有N的约数，那么分解N，dfs求约数。
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[100010]; 13 int ans[100010]; 14 int ak[105]; 15 int cnt[105]; 16 int p; 17 int fin[100001]; 18 int oula[100010]; 19 const int mod = 1000000007; 20 void slove(LL n); 21 void dfs(int n,int m,int c,int r); 22 int quick(int n,int m); 23 int main(void) 24 { 25 int T; 26 LL n; 27 scanf("%d",&T); 28 int i,j; 29 for(i = 2; i < 1000; i++) 30 { 31 if(!prime[i]) 32 { 33 for(j = i; (i*j) <= 100005; j++) 34 { 35 prime[i*j] = true; 36 } 37 } 38 } 39 int cn = 0; 40 for(i = 2; i <= 100005 ; i++) 41 { 42 if(!prime[i]) 43 ans[cn++] = i; 44 } 45 while(T--) 46 { 47 scanf("%lld",&n); 48 slove(n); 49 } 50 return 0; 51 } 52 void slove(LL n) 53 { 54 int f = 0; 55 int c = 0; 56 int t = -1; 57 p = 0; 58 LL pp = n; 59 memset(cnt,0,sizeof(cnt)); 60 while(n > 1) 61 { 62 while(n%ans[f] == 0) 63 { 64 if(c == 0) 65 { 66 c = 1; 67 t++; 68 ak[t] = ans[f]; 69 cnt[t]++; 70 } 71 else cnt[t]++; 72 n/=ans[f]; 73 } 74 c = 0; 75 f++; 76 if(ans[f]*ans[f]>n) 77 break; 78 } 79 if(n>1) 80 { 81 t++; 82 ak[t]=n; 83 cnt[t]++; 84 } 85 dfs(0,t+1,1,1); 86 LL sum = 0; 87 int i; 88 for(i = 0; i < p; i++) 89 { 90 sum =(sum+((LL)oula[i]*(LL)fin[i]/2)%mod)%mod; 91 } 92 printf("%lld\n",(sum+1)*(LL)pp%mod); 93 } 94 void dfs(int n,int m,int c,int r) 95 { 96 if(n == m) 97 { 98 fin[p] = c; 99 oula[p++] = r;100 return ;101 }102 int s = 1;103 int i;104 for(i = 0; i <= cnt[n]; i++)105 {106 if(s==1)107 {108 dfs(n+1,m,c*s,r);109 }110 else111 {112 dfs(n+1,m,c*s,r*s/ak[n]*(ak[n]-1));113 }114 s *= ak[n];115 }116 }
1363 最小公倍数之和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。