BZOJ 1101: [POI2007]Zap(莫比乌斯反演)
Posted On 2018年5月17日
Description
FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a
,y<=b,并且gcd(x,y)=d。作为FGD的同学,FGD希望得到你的帮助。
Input
第一行包含一个正整数n,表示一共有n组询问。(1<=n<= 50000)接下来n行,每行表示一个询问,每行三个
正整数,分别为a,b,d。(1<=d<=a,b<=50000)
Output
对于每组询问,输出到输出文件zap.out一个正整数,表示满足条件的整数对数。
Sample Input
2
4 5 2
6 4 3
4 5 2
6 4 3
Sample Output
3
2
//对于第一组询问,满足条件的整数对有(2,2),(2,4),(4,2)。对于第二组询问,满足条件的整数对有(
6,3),(3,3)。
2
//对于第一组询问,满足条件的整数对有(2,2),(2,4),(4,2)。对于第二组询问,满足条件的整数对有(
6,3),(3,3)。
HINT
Source
Solution
题目要求:
\(\sum_{i=1}^a \sum_{j=1}^b[gcd(i,j)==d]\)
令\(a’=\lfloor a/d \rfloor\),\(b’=\lfloor b/d \rfloor\)
原式\(=\sum_{i=1}^{a’} \sum_{j=1}^{b’}[gcd(i,j)==1]\)
\(=\sum_{i=1}^{a’} \sum_{j=1}^{b’}\sum_{d|gcd(i,j)}\mu (d)\) \(=\sum^{a’}_{d=1}\mu (d)\lfloor a’/d \rfloor\lfloor b’/d \rfloor\)筛完莫比乌斯函数后分块求解即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <algorithm> #include <cstdio> const int maxn=50100; char s[maxn*30],*c,o[maxn*30],*p=o; int cnt; inline int read() { register int f=1,k=0; while (*c<'0'||*c>'9')*c++=='-'&&(f=-1); while (*c>='0'&&*c<='9')k=k*10+*c++-'0'; return k*f; } inline void write(int x) { if (x<0)o[cnt++]='-',x=-x; register char tmp[10];register int now=0; do{tmp[now++]=x%10+'0';x/=10;}while(x); while(--now>=0)o[cnt++]=tmp[now]; o[cnt++]='\n'; } inline int min(const int&a,const int&b){return a<b?a:b;} int mu[maxn],not_prime[maxn],prime[maxn],sum[maxn],tot; inline int query(int n,int m) { if (n>m)std::swap(n,m); register int ans=0,pos; for (register int i=1;i<=n;i=pos+1) { pos=min(n/(n/i),m/(m/i)); ans+=(sum[pos]-sum[i-1])*(n/i)*(m/i); } return ans; } int main() { fread(c=s,1,sizeof(s),stdin); mu[1]=1; for (register int i=2;i<=50000;i++) { if (!not_prime[i])prime[++tot]=i,mu[i]=-1; for (register int j=1;j<=tot&&prime[j]*i<=50000;j++) { not_prime[prime[j]*i]=1; if (!(i%prime[j])) { mu[prime[j]*i]=0; break; } mu[prime[j]*i]=-mu[i]; } } for (register int i=1;i<=50000;i++)sum[i]=sum[i-1]+mu[i]; for (int T=read();T;T--) { int a=read(),b=read(),d=read(); write(query(a/d,b/d)); } fwrite(o,1,cnt,stdout); } |
Subscribe
0 评论