题目:GCD SUM
题目链接:http://www.bnuoj.com/v3/problem_show.php?pid=39872
算法:莫比乌斯反演、优化
#include<stdio.h>
#define N 100001
typedef long long LL;
bool pri[N]={};
int prim[N],po=;
int mu[N];
LL f[N],ff[N]; //缩短时间
/*
莫比乌斯函数mu[i]的定义:
1. 如果 i 是素数,那么mu[i]为-1;
2. 如果 i 是由多个不同的素数组成的,那么mu[i]为-1或者1,取决于质因子的数量,奇数就为-1,偶数为1
3. 如果 i 不满上面的条件,那么mu[i]为0,比如mu[4]=0;
用途:想要判断1~m中有多少数与i互质,那么首先计算出i的质因子,采用容斥定理做,排除掉所有质因子的倍数,再加上被重复计算的
比如i=6、m=20时,首先排除2的倍数,再排除3的倍数,现在6的倍数被排除两次,就加上6的倍数数量。
*/
void Init()
{
mu[]=;
for(int i=;i<N;i++)
{
if(!pri[i])
{
prim[po++]=i;
mu[i]=-;
}
for(int j=;j<po;j++)
{
LL tmp=i*prim[j];
if(tmp>=N) break;
pri[tmp]=;
mu[tmp]=mu[i]*-;
if(i%prim[j]==)
{
mu[tmp]=;
break;
}
}
}
f[]=ff[]=;
//f[]:mu的前缀和
for(int i=;i<N;i++)
{
f[i]=f[i-]+mu[i];
ff[i]=ff[i-]+mu[i]*i;
}
}
int min(int n,int m)
{
return n>m?m:n;
}
int main()
{
Init();
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
LL ans=,ansx=,ansy=;
int t=min(n,m);
int j=;
/*
简化前:
for(int i=1;i<=t;i++)
{
ans+=mu[i]*(n/i)*(m/i);
可简化原因:(n/i)*(m/i)虽然i一直在变化,但很多时候是相等的,比如15/8等于1,一直到15/15还是等于1。。。
ansx+=mu[i]*(m/i)*(i+(n/i)*i)*(n/i)/2;
...
}
n/i:得到值,随着i的增大,如果这个值一直不变,那么这些可以和在一起算。
n/(n/i):得到上面值得最大i,从上面的i到现在的i=n/(n/i),之间的n/i,都等于n/i
*/
for(int i=;i<=t;i=j+)
{
j=min(n/(n/i),m/(m/i));
ans+=(f[j]-f[i-])*(n/i)*(m/i);
ansx+=(ff[j]-ff[i-])*(m/i)*(+(n/i))*(n/i)/;
ansy+=(ff[j]-ff[i-])*(n/i)*(+(m/i))*(m/i)/;
}
printf("%lld %lld %lld\n",ans,ansx,ansy);
}
return ;
}