BZOJ 2301: [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

题解

好吧,我知道这题我以前做过了,但是印象不太深了QuQ相当于重做了一遍Orz、、、、
(\sum_{x=a}^{b}\sum_{y=c}^{d}[gcd(x,y)=k]=\sum_{x=\frac{a}{k}}^{\frac{b}{k}}\sum_{y=\frac{c}{k}}^{\frac{d}{b}}[gcd(x,y)=1]=\sum_{x=\frac{a}{k}}^{\frac{b}{k}}\sum_{y=\frac{c}{k}}^{\frac{d}{b}}\sum_{z=1}^{min{x,y}}u(z)×⌊\frac{x}{z}⌋×⌊\frac{y}{z}⌋)

代码