[POI2007]Zap

[POI2007]Zap

Time Limit:10000MS Memory Limit:165536K
Total Submit:176 Accepted:34
Case Time Limit:2000MS

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

Sample Output

Hint

对于第一组询问,满足条件的整数对有(2,2),(2,4),(4,2)。
对于第二组询问,满足条件的整数对有(6,3),(3,3)。

Source
额。。这题十分的那个啥。。。。Orz oimaster神牛!!!
首先对付这种复杂的问题只有容斥原理了。。
只需要算出G(x,y):1<=i<=a,1<=j<=b且(i,j)=1的就可以了。。
F(a,b,k)表示1<=i<=a,1<=j<=b且(i,j)>=k的对数,很显然为a/k*b/k。。
那么G(a,b)=1*F(a,b,1)-F(a,b,2)….注意对每个k来说,无论a和b,系数是固定的。。
同时a/k*b/k按相同值分段可以分成Sqrt级别。。所以预处理一下系数的部分和就OK了。。
代码长度最短囧。。。

#include <algorithm>#include <cstdio>#define rep(i,n) for(int i=0;i<n;i++)const int maxn=50000+10;using namespace std;int P[maxn]={};int get(int i){ int s=1; for(int x=2;x*x<=i;x++)if(i%x==0) { i/=x;if(i%x==0)return 0; s*=-1; } if(i>1)s*=-1; return s;}int main(){ for(int i=1;i<=maxn;i++)P[i]=P[i-1]+get(i); int a,b,k,n;scanf("%d",&n); rep(i,n) { scanf("%d%d%d",&a,&b,&k);a/=k;b/=k; if(a>b)swap(a,b); int ans=0; for(int t=1;t<=a;t++) { int m=min(a/(a/t),b/(b/t))-t; ans+=(P[t+m]-P[t-1])*(a/t)*(b/t); t+=m; } printf("%dn",ans); }}3224 5 26 4 3

11 thoughts on “[POI2007]Zap

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>