首页 > 代码库 > BNU 12846 LCM Extreme 最小公倍数之和(线性欧拉筛选+递推)
BNU 12846 LCM Extreme 最小公倍数之和(线性欧拉筛选+递推)
LCM Extreme
3000ms
131072KB
This problem will be judged on UVALive. Original ID: 5964
64-bit integer IO format: %lld Java class name: Main
64-bit integer IO format: %lld Java class name: Main
Find the result of the following code:
unsigned long long allPairLcm(int n){
unsigned long long res = 0;
for( int i = 1; i<=n;i++)
for(int j=i+1;j<=n;j++)
res += lcm(i, j);// lcm means least common multiple
return res;
}
A straight forward implementation of the code may time out.
Input
Input starts with an integer T (≤ 25000), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 5*106
).
Output
For each case, print the case number and the value returned by the function ‘allPairLcm(n)‘. As the
result can be large, we want the result modulo 2
64
.
Sample Input Output for Sample Input
4
2
10
13
100000
Case 1: 2
Case 2: 1036
Case 3: 3111
Case 4: 9134672774499923824
1 /* 2 题目大意:求lcm(1,2)+lcm(1,3)+lcm(2,3)+....+lcm(1,n)+....+lcm(n-2,n)+lcm(n-1,n) 3 设sum(n)为sum(lcm(i,j))(1<=i<j<=n)之间最小公倍数的和,f(n)为sum(i*n/gcd(i,n))(1<=i<n) 4 那么sum(n)=sum(n-1)+f(n)。可以用线性欧拉筛选+递推来做。 5 */ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 10 typedef unsigned long long LL;11 const int maxn=5000005;12 LL phi[maxn],sum[maxn],f[maxn];13 14 void Euler()15 {16 memset(phi,0,sizeof(phi));17 int i,j;phi[1]=1;18 for(i=2;i<maxn;i++)19 {20 if(phi[i]) continue;21 for(j=i;j<maxn;j+=i)22 {23 if(!phi[j]) phi[j]=j;24 phi[j]=phi[j]/i*(i-1);25 }26 }27 for(i=1;i<maxn;i++) phi[i]=phi[i]*i/2;//与i互质的数之和28 }29 30 void init()31 {32 Euler();33 memset(sum,0,sizeof(sum));34 memset(f,0,sizeof(f));35 int i,j;sum[1]=f[1]=0;36 for(i=2;i<maxn;i++)37 {38 f[i]+=phi[i]*i;//与i互质的数之间的lcm之和39 for(j=2*i;j<maxn;j+=i)40 f[j]+=phi[i]*j;//gcd(x,j)=i的sum(lcm(x,j))41 sum[i]=sum[i-1]+f[i];42 }43 }44 45 int main()46 {47 //freopen("in.txt","r",stdin);48 //freopen("out.txt","w",stdout);49 init();50 int t,icase=0,n;51 scanf("%d",&t);52 while(t--)53 {54 scanf("%d",&n);55 printf("Case %d: %llu\n",++icase,sum[n]);56 }57 return 0;58 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。