No.3687 Coprime Count
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 30
作問者 :
Unbakedbread
/ テスター :
Tamiji153
タグ : / 解いたユーザー数 30
作問者 :
Unbakedbread
/ テスター :
Tamiji153
問題文最終更新日: 2026-08-07 14:51:06
問題文
正整数 $N,M$ が与えられます。
$N$ 以下の正整数 $a$ と $M$ 以下の正整数 $b$ の組であって、 $a$ と $b$ の最大公約数が $1$ であるようなものの個数を求めてください。
制約
- $N,M$ は $1$ 以上 $10^7$ 以下の整数
入力
$N\ M$
出力
答えを出力せよ。サンプル
サンプル1
入力
3 5
出力
12
$(a,b)=(1,1),(1,2),(1,3),(1,4),(1,5),(2,1),(2,3),(2,5),(3,1),(3,2),(3,4),(3,5)$ の $12$ 個です。
サンプル2
入力
13 31
出力
266
サンプル3
入力
10000000 10000000
出力
60792712854483
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。