2671: Calc
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 303 Solved: 157Description
给出N，统计满足下面条件的数对(a,b)的个数：
1.1<=a<b<=N
2.a+b整除a*bInput
一行一个数N
Output
一行一个数表示答案
Sample Input
15Sample Output
4HINT
数据规模和约定
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
【分析】
这题的复杂度还挺迷人的。
然后$\sqrt n$也没发现，以为筛$\mu$都要$O(n)$,什么杜教筛的幸好不会。。
首先分析$(a+b)|(a*b) → (a/g+b/g)|(a/g*b/g*g) →(a/g+b/g)|g$
那就是互质的$a',b'$ 找他们的公倍数$g$就行了。
写正常一点就是$$\sum_{j=1}^{N}\sum_{i=1}^{j-1}\dfrac{n}{j*(i+j)} [gcd(i,j)==1]$$
到了这里，我就傻眼了，其实嘛。。。j并不会到$n$，只是到$\sqrt{n}$
$$\sum_{j=1}^{\sqrt{n}}\sum_{i=1}^{j-1}\dfrac{n}{j*(i+j)} [gcd(i,j)==1]$$
然后我又傻眼了，复杂度迷人的东西啊会把我脑子弄得很乱的。
直接枚举j，然后i那里分块，然后就是求[l,r]里面和j互质的数的个数。
差分，先求[1,r]里面的，就是$\sum_{x=1}^{r}1[gcd(x,j)==1]$
即$\sum_{d=1}^{r}\mu(d)*(r/d)$
最后就是$\sum_{d=1}^{r}\mu(d)*(r/d-(l-1)/d)$
枚举约数在前面$\sqrt{j}$枚举去了。。
真的是暴力出奇迹了。。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define Maxn 50010
#define LL long long bool vis[Maxn];
int pri[Maxn],pl,mu[Maxn]; int mymin(int x,int y) {return x<y?x:y;} void init()
{
memset(vis,,sizeof(vis));
pl=;mu[]=;
for(int i=;i<=Maxn;i++)
{
if(!vis[i]) pri[++pl]=i,vis[i]=,mu[i]=-;
for(int j=;j<=pl;j++)
{
if(i*pri[j]>Maxn) break;
vis[i*pri[j]]=;
if(i%pri[j]==) {mu[i*pri[j]]=;break;}
mu[i*pri[j]]=-mu[i];
}
}
} int sta[Maxn],sl; void div(int x)
{
sl=;
int i;
for(i=;i*i<x;i++)
{
if(x%i==) sta[++sl]=i,sta[++sl]=x/i;
}
if(i*i==x) sta[++sl]=i;
} int gcd(int a,int b)
{
if(b==) return a;
return gcd(b,a%b);
} int main()
{
int n;
scanf("%d",&n);
init();
LL ans=;
int sq=(int)(sqrt((double)n));
for(int i=;i<=sq;i++)
{
div(i);
for(int j=;j<i;)
{
int x=n/i/(i+j),r;if(x==) break;
r=mymin(i-,n/x/i-i);
for(int k=;k<=sl;k++)
{
ans+=mu[sta[k]]*(r/sta[k]-(j-)/sta[k])*x;
}
j=r+;
}
}
printf("%lld\n",ans);
return ;
}
2017-04-06 15:50:26