Pro.ID10042 TitleNumber Title链接http://10.20.2.8/oj/exercise/problem?problem_id=10042 AC12 Submit73 Ratio16.44% 时间&空间限制描述有两个数A和B ( 0 < A ≤ B )。如果B不能被A整除,且A和B不互质,我们定义A是B的一个"特数"。 对每个x,定义f(x)等于x的"特数"个数。 例如,f(6)=1,因为6仅有一个特数4。f(12)=3,它有3个特数8,9,10。 当f(x)的值为奇数时,我们称x是一个"真数"。 现在给出两个整数x和y,你的任务就是计算它们之间有多少个"真数"。 输入第一行有一个整数T ( T ≤ 2000 ),表示测试用例的个数。 接下来T行,每行两个整数x和y ( 1 ≤ x ≤ y ≤ 263-1 )。 输出Description 有两个数A和B ( 0 < A ≤ B )。如果B不能被A整除,且A和B不互质,我们定义A是B的一个"特数"。 对每个x,定义f(x)等于x的"特数"个数。 例如,f(6)=1,因为6仅有一个特数4。f(12)=3,它有3个特数8,9,10。 当f(x)的值为奇数时,我们称x是一个"真数"。 现在给出两个整数x和y,你的任务就是计算它们之间有多少个"真数"。 Input 第一行有一个整数T ( T ≤ 2000 ),表示测试用例的个数。 接下来T行,每行两个整数x和y ( 1 ≤ x ≤ y ≤ 263-1 )。 Output 为每个测试用例输出一行,x和y之间"真数"的个数。 Sample Input 2 Sample Output 0 Hint 第二个例子里,4个真数是 6,8,9,10。 Source 样例输入2 样例输出0 提示第二个例子里,4个真数是 6,8,9,10。 |