G. 【普及】最大公约数计数

    传统题 100ms 32MiB

【普及】最大公约数计数

【普及】最大公约数计数

给定正整数 nn 和 dd,请问 1∼n1 \sim n 中有多少个数 xx 满足 xx 和 nn 的最大公约数是 dd;

即求满足 gcd(x,n)=dgcd(x, n) = d 的 xx 的个数。

输入格式

第一行,一个整数 TT 代表数据组数;接下来 TT 组数据

每组数据包含 22 个正整数代表 nn 和 dd

输出格式

对于每组数据输出一行,包含答案

1
12 2
2

提示

【样例 1 解释】

  • gcd⁡(2,12)=2,gcd⁡(10,12) = 2\gcd(2, 12) = 2, \gcd(10, 12)\ =\ 2
  • 其他数不满足,比如 gcd⁡(8,12) = 4\gcd(8, 12)\ =\ 4

【数据范围】

  • 1≤T≤1061 \le T \le 10^6
  • 1≤d≤n≤1061 \le d \le n \le 10^6
请思考后再点击查看提示

来源