首页 > 代码库 > BZOJ1101: [POI2007]Zap

BZOJ1101: [POI2007]Zap

2024-07-21 12:14:39   232人阅读

1101: [POI2007]Zap

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1268  Solved: 399
[Submit][Status]

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

Sample Output

3
2

HINT

 

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

 

Source

题解：

贾志鹏线性筛。

分块的技巧基于：

 n/(n/i)为 拥有 n/j=n/i 性质的最大的j ，也就是从i --n/(n/i)这一段 n 除它们的商相等

比如 100/34=2    100/（100/34）=100/2=50   34-50这一段被n除的商都是2

为什么呢？ 这是因为我们对100可以这样分解

100=34*2+32   32比34小，作为余数

100=2*50+0     0比2小，作为余数

也就是说，我们只要把第一次的除法的余数分配到（n/i）的系数上，就可以尽可能的保持，n/i不变，而它的系数尽可能大，显然不能在分过去的时候，n/i的系数达到的了最大。

而这刚好就是n/(n/i)

说了一堆废话。。。

代码：

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 50000+100014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 using namespace std;22 inline int read()23 {24     int x=0,f=1;char ch=getchar();25     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}26     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}27     return x*f;28 }29 int p[maxn],mu[maxn],sum[maxn];30 bool check[maxn];31 void get()32 {33     int tot=0;34     mu[1]=1;35     for2(i,2,maxn)36     {37         if(!check[i])p[++tot]=i,mu[i]=-1;38         for1(j,tot)39          {40              int k=p[j]*i;41              if(k>maxn)break;42             check[k]=1;43             if(i%p[j])mu[k]=-mu[i];else {mu[k]=0;break;}44          }45     }46     for1(i,maxn)sum[i]=sum[i-1]+mu[i];47 }48 int main()49 {50     freopen("input.txt","r",stdin);51     freopen("output.txt","w",stdout);52     get();53     int cs=read();54     while(cs--)55      {56          ll n=read(),m=read(),x=read(),ans=0;57          n/=x;m/=x;58          if(n>m)swap(n,m);59          for(int s=1,t;s<=n;s=t+1)60           {61               t=min(n/(n/s),m/(m/s));62               ans+=(n/s)*(m/s)*(sum[t]-sum[s-1]);63           }64          printf("%lld\n",ans); 65      }66     return 0;67 }
View Code

 

BZOJ1101: [POI2007]Zap


联系
我们