【转】UVALive 5964 LCM Extreme --欧拉函数

题目大意:求lcm(1,2)+lcm(1,3)+lcm(2,3)+....+lcm(1,n)+....+lcm(n-2,n)+lcm(n-1,n)
解法:设sum(n)为sum(lcm(i,j))(1<=i<j<=n)之间最小公倍数的和,
f(n)为sum(i*n/gcd(i,n))(1<=i<n)
那么sum(n)=sum(n-1)+f(n)。
可以用线性欧拉筛选+递推来做。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 207 typedef unsigned long long LL;
const int maxn=;
LL phi[maxn],sum[maxn],f[maxn]; void Euler()
{
memset(phi,,sizeof(phi));
int i,j;
phi[]=;
for(i=;i<maxn;i++)
{
if(phi[i])
continue;
for(j=i;j<maxn;j+=i)
{
if(!phi[j])
phi[j]=j;
phi[j]=phi[j]/i*(i-);
}
}
for(i=;i<maxn;i++)
phi[i]=phi[i]*i/; //与i互质的数之和
} void init()
{
Euler();
memset(sum,,sizeof(sum));
memset(f,,sizeof(f));
int i,j;
sum[]=f[]=;
for(i=;i<maxn;i++)
{
f[i]+=phi[i]*i; //与i互质的数之间的lcm之和
for(j=*i;j<maxn;j+=i)
f[j]+=phi[i]*j; //gcd(x,j)=i的sum(lcm(x,j))
sum[i]=sum[i-]+f[i];
}
} int main()
{
init();
int t,icase=,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("Case %d: %llu\n",++icase,sum[n]);
}
return ;
}
上一篇:Ubuntu16.04下的NetCore环境搭建(附录含Ubuntu 18.04 安装 NetCore2.1)


下一篇:SSE图像算法优化系列二十六:和时间赛跑之优化高斯金字塔建立的计算过程。