obsidian

BZOJ 2818 Gcd(莫比乌斯反演)

26
2017/08

# 题目

## Sample Input

4

## Sample Output

4

# 分析

$$ans=\sum_{p}^{min(n,m)} \sum_{d=1}^{min(n,m)} \mu(d) \left\lfloor\frac{n}{pd}\right\rfloor \left\lfloor\frac{m}{pd}\right\rfloor$$

$$ans=\sum_{T=1}^{min(n,m)}\left\lfloor\frac{n}{T}\right\rfloor \left\lfloor\frac{m}{T}\right\rfloor \sum_{p|T} \mu(\frac{T}{p})$$

const int MAXN=100010;
bool vis[MAXN];
int tot,phi[MAXN],prime[MAXN];
void CalPhi(int n)
{
clr(vis,0);
phi[1]=1;
tot=0;
for(int i=2;i<n;i++)
{
if(!vis[i])
{
prime[tot++]=i;
phi[i]=i-1;
}
for(int j=0;j<tot;j++)
{
if(i*prime[j]>n) break;
vis[i*prime[j]] == 1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i] * prime[j];
break;
}
else phi[i*prime[j]]=phi[i] * (prime[j]-1);
}
}
}

# 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<functional>
#include<climits>
#include<cctype>
#include<iomanip>
#include<bitset>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define clr(a,x) memset(a,x,sizeof(a))
const double eps = 1e-6;
const int mod = 1e9+7;
const int MAXN=10000010;
int a[MAXN]={1,1},b[MAXN/10],mu[MAXN],cnt;
void init()
{
ll i,j;
mu[1]=1;
for(int i=2;i<MAXN;i++)
{
if(a[i]==0)
{
b[++cnt]=i;
mu[i]=-1;
}
for(int j=1;j<=cnt&&b[j]*i<MAXN;j++)
{
a[b[j]*i]=1;
if(i%b[j]==0)
{
mu[b[j]*i]=0;
break;
}
else
{
mu[b[j]*i]=-mu[i];
}
}
}
}
int main()
{
init();
int n;
ll ans=0;
scanf("%d",&n);
for(int i=1;i<=cnt&&b[i]<=n;i++)
{
ll sum=0;
for(int j=b[i];j<=n;j+=b[i])
sum+=(ll)mu[j/b[i]]*(n/j)*(n/j);
ans+=sum;
}
printf("%lld\n",ans);
return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<functional>
#include<climits>
#include<cctype>
#include<iomanip>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define clr(a,x) memset(a,x,sizeof(a))
const double eps = 1e-6;
const int mod = 1e9+7;
const int MAXN=1e7 + 5;
bool vis[MAXN];
int tot,phi[MAXN],prime[MAXN];

//refer to CSL

void CalPhi(int n)
{
clr(vis,0);
phi[1]=1;
tot=0;
for(int i=2;i<n;i++)
{
if(!vis[i])
{
prime[tot++]=i;
phi[i]=i-1;
}
for(int j=0;j<tot;j++)
{
if(i*prime[j]>n) break;
vis[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
ll a[MAXN];
int main()
{
int n;
ll ans=0;
scanf("%d",&n);
CalPhi(n);
a[1]=1;
for(int i=2;i<=n;i++)
a[i]=a[i-1]+2*phi[i];
for(int i=0;i<tot;i++)
if(n/prime[i])
ans+=a[n/prime[i]];
printf("%lld\n",ans);
return 0;
}


Last modification：November 2nd, 2019 at 03:03 pm