TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3957
  • Problem
  • P3957YY的GCD
    Limits : Time Limit : - MS   Memory Limit : 565536 KB
    Judgment Tips : 1s
    Description

    神犇YY虐完数论后给傻×kAc出了一题 
    给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对 
    kAc这种傻×必然不会了,于是向你来请教…… 
    多组输入

    Input Format

    第一行一个整数T 表述数据组数

    接下来T行,每行两个正整数,表示N, M

    Output Format

    T行,每行一个整数表示第i组数据的结果

    Sample Input 1

    2
    10 10
    100 100

    Sample Output 1

    30
    2791

    Sample Input 2

    5
    555 785
    450 317
    28 26
    284 132
    602 341

    Sample Output 2

    120008
    39145
    207
    10277
    56504

    Hint

    T = 10000

    N, M <= 10000000


    Source  bzoj 2820