WAC220.最大公约数

传统题 时间 2000 ms 内存 256 MiB 8 尝试 1 已通过 1 标签

最大公约数

给定整数 NN,求 1x,yN1 \le x,y \le NGCD(x,y)GCD(x,y) 为素数的数对 (x,y)(x,y) 有多少对。

GCD(x,y)GCD(x,y) 即求 xyx,y 的最大公约数。

输入格式

输入一个整数 NN

输出格式

输出一个整数,表示满足条件的数对数量。

数据范围

1N1071 \le N \le 10^7

Samples

4
4

在线编程 IDE

建议全屏模式获得最佳体验