- 标签 最大公约数,gcd 莫比乌斯反演 POI 2007 高性能
- 难度 省选/NOI-
- 时空限制 2s / 128MB
Byteasar the Cryptographer works on breaking the code of BSA (Byteotian Security Agency). He has alreadyfound out that whilst deciphering a message he will have to answer multiple queries of the form"for givenintegers $a$, $b$ and $d$, find the number of integer pairs $(x,y)$ satisfying the following conditions:
$1\le x\le a$,$1\le y\le b$,$gcd(x,y)=d$, where $gcd(x,y)$ is the greatest common divisor of $x$ and $y$".
Byteasar would like to automate his work, so he has asked for your help.
TaskWrite a programme which:
reads from the standard input a list of queries, which the Byteasar has to give answer to, calculates answers to the queries, writes the outcome to the standard output.
The first line of the standard input contains one integer $n$ ($1\le n\le 50\ 000$),denoting the number of queries.
The following $n$ lines contain three integers each: $a$, $b$ and $d$($1\le d\le a,b\le 50\ 000$), separated by single spaces.
Each triplet denotes a single query.输出格式：
Your programme should write $n$ lines to the standard output. The $i$'th line should contain a single integer: theanswer to the $i$'th query from the standard input.