#P2257. YY的GCD
YY的GCD
题目描述
神犇 YY 虐完数论后给傻× kAc 出了一题
给定 ,求 , 且 为质数的 有多少对。
输入格式
第一行一个整数 表述数据组数。
接下来 行,每行两个正整数,。
输出格式
行,每行一个整数表示第 组数据的结果。
2
10 10
100 100
30
2791
提示
,。
神犇 YY 虐完数论后给傻× kAc 出了一题
给定 N,M,求 1≤x≤N,1≤y≤M 且 gcd(x,y) 为质数的 (x,y) 有多少对。
第一行一个整数 T 表述数据组数。
接下来 T 行,每行两个正整数,N,M。
T 行,每行一个整数表示第 i 组数据的结果。
2
10 10
100 100
30
2791
T=104,N,M≤107。