• 应用
• 登录
• 注册

# P3455 [POI2007]ZAP-Queries

• 183通过
• 415提交
• 题目提供者洛谷OnlineJudge
• 标签 最大公约数,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.

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.

FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a，y<=b，并且gcd(x,y)=d。作为FGD的同学，FGD希望得到你的帮助。

## 输入输出格式

输入格式：

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.

## 输入输出样例

输入样例#1： 复制
2
4 5 2
6 4 3
输出样例#1： 复制
3
2
提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。