bzoj 2671 莫比乌斯反演

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

Sample Output

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.csdn.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);

 }

巴特西