BZOJ 2005 2005: [Noi2010]能量采集 | 容斥原理

时间:2023-08-08 22:20:14

题目:

http://www.lydsy.com/JudgeOnline/problem.php?id=2005


题解:

http://blog.csdn.net/popoqqq/article/details/39924877

#include<cstdio>
#include<algorithm>
#define N 100005
using namespace std;
typedef long long ll;
ll phi[N],su[N],sum[N];
bool he[N];
void Euler(int n)
{
int tot=;
phi[]=;
for(int i=;i<=n;i++)
{
if(!he[i])
{
su[++tot]=i;
phi[i]=i-;
}
for(int j=;j<=tot;j++)
{
if(i*su[j]>=n)break;
he[i*su[j]]=;
if(i%su[j]==)
{
phi[i*su[j]]=phi[i]*su[j];break;
}
else phi[i*su[j]]=phi[i]*(su[j]-);
}
}
for(int i=;i<=n;i++)
phi[i]+=phi[i-];
return;
}
int main(){
ll n,m,ans=;
scanf("%lld%lld",&n,&m);
if(n>m)swap(n,m);
Euler(n+);
for(ll i=,j;i<=n;i=j+)
{
j=min(n/(n/i),m/(m/i));
ans+=(ll)(phi[j]-phi[i-])*(n/i)*(m/i);
}
printf("%lld\n",*ans-n*m);
return ;
}