「BZOJ2301」[HAOI2011] Problem b
Description
对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。
Input
第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k
Output
共n行，每行一个整数表示满足要求的数对(x,y)的个数
Sample Input
2
2 5 1 5 1
1 5 1 5 2
Sample Output
14
3
HINT
100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000
题解
同bzoj1101T T
就是区间加加减减啥的
|
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 61 62 63 64 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<cmath> #include<algorithm> #include<map> #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int tot; int a,b,c,d,k; int sum[50005],mu[50005],pri[50005]; bool mark[50005]; void getmu() { mu[1]=1; for(int i=2;i<=50000;i++) { if(!mark[i]){mu[i]=-1;pri[++tot]=i;} for(int j=1;j<=tot&&i*pri[j]<=50000;j++) { mark[i*pri[j]]=1; if(i%pri[j]==0){mu[i*pri[j]]=0;break;} else mu[i*pri[j]]=-mu[i]; } } for(int i=1;i<=50000;i++) sum[i]=sum[i-1]+mu[i]; } int cal(int n,int m) { if(n>m)swap(n,m); int ans=0,pos; for(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() { getmu(); int T=read(); while(T--) { a=read();b=read();c=read();d=read();k=read(); a--;c--; a/=k;b/=k;c/=k;d/=k; int ans=cal(a,c)+cal(b,d)-cal(a,d)-cal(b,c); printf("%d\n",ans); } return 0; } |
Subscribe
计数器 9855210
OI 课件=>
OI 课件=>