UOJ Logo LFYZ Online Judge

LFYZOJ

#59. 【模板】莫比乌斯反演(【HAOI2011】Problem b)

统计

问题描述

对于给出的 $n$ 个询问,每次求有多少个数对 $(x,y)$,满足 $a \leq x \leq b$,$c \leq y \leq d$,且 $\gcd(x,y) = k$。

输入格式

第一行一个整数 $n$,接下来 $n$ 行每行五个整数,分别表示 $a,b,c,d,k$。

输出格式

共 $n$ 行,每行一个整数表示满足要求的数对 $(x,y)$ 的个数。

样例一

input

2
2 5 1 5 1
1 5 1 5 2

output

14
3

数据范围与约定

对于 $100\%$ 的数据,$1 \leq n \leq 50000$,$1 \leq a \leq b \leq 50000$,$1 \leq c \leq d \leq 50000$,$1 \leq k \leq 50000$。

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$