题目名称	2602. [BZOJ 2818]GCD
输入输出	`gcd_prime.in/out`
难度等级	★★☆
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	syzhaoss 于2017-01-24加入
开放分组	全部用户
提交状态
分类标签	最大公约数欧拉函数素数筛法数学数论
	分享题解

通过：7，提交：14，通过率：50%
mxr2022	100	0.346 s	50.36 MiB	C++
ムラサメ	100	0.372 s	40.10 MiB	C++
┭┮﹏┭┮	100	0.442 s	50.36 MiB	C++
SKG_G	100	0.516 s	52.65 MiB	C++
nick	100	0.986 s	51.88 MiB	C++
00000	100	1.903 s	95.17 MiB	C++
lihaoze	100	2.455 s	168.01 MiB	C++
nick	80	0.931 s	52.00 MiB	C++
00000	60	0.974 s	63.45 MiB	C++
00000	50	0.936 s	46.66 MiB	C++

关于 GCD 的近10条评论(全部评论)

2602. [BZOJ 2818]GCD

★★☆ 输入文件：gcd_prime.in 输出文件：gcd_prime.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

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

【输入格式】

第一行一个整数 $N$。

【输出格式】

一个整数表示满足条件的对数。

【样例输入】

【样例输出】

【样例解释】

对于样例，满足条件的对为(2,2),(2,4),(3,3),(4,2)。

【数据范围】

$1\leq N\leq 10^7$