bzoj 2671 莫比乌斯反演

时间:2025-03-25 14:34:07

Calc

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 451  Solved: 234
[Submit][Status][Discuss]

Description

  给出N,统计满足下面条件的数对(a,b)的个数:
  1.1<=a<b<=N
  2.a+b整除a*b

Input

 一行一个数N

Output

 一行一个数表示答案

Sample Input

15

Sample Output

4

HINT

数据规模和约定

Test N Test N

1 <=10 11 <=5*10^7

2 <=50 12 <=10^8

3 <=10^3 13 <=2*10^8

4 <=5*10^3 14 <=3*10^8

5 <=2*10^4 15 <=5*10^8

6 <=2*10^5 16 <=10^9

7 <=2*10^6 17 <=10^9

8 <=10^7 18 <=2^31-1

9 <=2*10^7 19 <=2^31-1

10 <=3*10^7 20 <=2^31-1

Source

[Submit][Status][Discuss]

HOME Back

http://blog.****.net/popoqqq/article/details/45095601

 #pragma GCC optimize(2)
#pragma G++ optimize(2)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
#define mod 1000000007
#define N 50005
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} bool flag[N];
int tot,p[N],miu[N],n,m,pos;
ll ans; void pre()
{
miu[]=;
for (int i=;i<N;i++)
{
if (!flag[i]) p[++tot]=i,miu[i]=-;
for (int j=;j<=tot&&p[j]*i<N;j++)
{
flag[i*p[j]]=;
if (i%p[j]==) break;
miu[i*p[j]]=-miu[i];
}
}
}
int main()
{
pre();
scanf("%d",&n);m=sqrt(n);
for (int d=;d<=m;d++)
{
for (int i=;i<=m/d;i++)
{
int last=n/(d*d*i);
for (int x=i+,p=;x<=*i-&&x<=last;x=pos+)
{
pos=last/(last/x);
ans+=1LL*miu[d]*(min(pos,*i-)-x+)*(last/x);
}
}
}
printf("%lld",ans);
}