| 题目名称 | 2165. [BZOJ 2820] YY的GCD |
|---|---|
| 输入输出 | YYnoGCD.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 mikumikumi
于2016-02-23加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 查看题解 | 分享题解 |
| 通过：100， 提交：221， 通过率：45.25% | ||||
 BPM136 |
100 | 8.472 s | 162.44 MiB | C++ |
 Cooook |
100 | 8.730 s | 238.81 MiB | C++ |
|
Cooook |
100 | 8.976 s | 238.81 MiB | C++ |
|
Cooook |
100 | 9.452 s | 238.81 MiB | C++ |
 瑆の時間~無盡輪迴·林蔭 |
100 | 9.495 s | 166.25 MiB | C++ |
 lihaoze |
100 | 9.530 s | 129.71 MiB | C++ |
 New World |
100 | 9.885 s | 124.40 MiB | C++ |
 kito |
100 | 9.970 s | 93.83 MiB | C++ |
|
┭┮﹏┭┮ |
100 | 10.015 s | 167.86 MiB | C++ |
 xzy |
100 | 10.080 s | 94.70 MiB | C++ |
| 关于 YY的GCD 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
这一题有些玄学。。。不该开 long long 的地方不开 long long 会省一些时间。
| ||||
|
COGS该换了，同样一份代码，在不同时间测试，差了20分
| ||||
|
不要告诉我文件名的那个no是の
QWQ | ||||
|
kito教会线性筛？
| ||||
|
1A率感人
 祖国栋梁
2017-03-30 11:50
19楼
| ||||
|
回复 @FoolMike :
愿闻其详。  AntiLeaf
2017-02-22 14:39
18楼
| ||||
|
回复 @AntiLeaf :
我校神犇教会了我O(n)做法  FoolMike
2017-02-22 13:48
17楼
| ||||
|
回复 @FoolMike :
并不知道为什么……反正打表观察运算次数和实测都表明复杂度大概是$O(n\log\log n)$…… AntiLeaf
2017-02-18 19:40
16楼
| ||||
|
回复 @AntiLeaf :
质数的个数是O(n/logn)的，然后每个质数p需要O(n/p)的时间处理，我怎么觉得是O(nlogn)的复杂度啊 FoolMike
2017-02-18 17:57
15楼
| ||||
|
回复 @FoolMike :
$O(n\log\log n)$，至于为什么我也不知道…… AntiLeaf
2017-02-12 20:29
14楼
| ||||
Hzoi_Mafia【题目描述】
给定 $N,M$，求 $1\le x\le N,1\le y\le M$ 且 $gcd(x,y)$ 为质数的 $(x,y)$ 有多少对。
【输入格式】
第一行一个整数 $T$ 表示数据组数。
接下来 $T$ 行，每行两个正整数，表示 $N,M$。
【输出格式】
$T$ 行，每行一个整数表示第i组数据的结果。
【样例输入】
2 10 10 100 100
【样例输出】
30 2791
【提示】
$T = 10000$
$N, M \le 10000000$
【来源】
BZOJ 2820