TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3957
  • 問題
  • P3957YY的GCD
    制限 : 時間制限 : - MS   メモリ制限 : 565536 KB
    審判説明 : 1s
    問題説明

    神犇YY虐完数论后给傻×kAc出了一题

    给定N, M,求 $1\le x\le N$ , $1\le y\le M$ 且 \(\gcd(x, y)\) 为质数的 \((x, y)\) 有多少对

    kAc这种傻×必然不会了,于是向你来请教……

    多组输入

    入力形式

    第一行一个整数 \(T\) 表述数据组数

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

    出力形式

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

    サンプル入力 1

    2
    10 10
    100 100

    サンプル出力 1

    30
    2791

    サンプル入力 2

    5
    555 785
    450 317
    28 26
    284 132
    602 341

    サンプル出力 2

    120008
    39145
    207
    10277
    56504

    ヒント

    $T = 10000 $

    \(N, M \le 10190000\)


    ソース  bzoj 2820