| 题目名称 | 656. 最大公约数 |
|---|---|
| 输入输出 | gcd.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2012-03-23加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：83， 提交：209， 通过率：39.71% | ||||
 xyz117 |
100 | 0.038 s | 0.40 MiB | C++ |
 神利·代目 |
100 | 0.087 s | 4.40 MiB | C++ |
|
神利·代目 |
100 | 0.087 s | 4.40 MiB | C++ |
|
神利·代目 |
100 | 0.089 s | 4.40 MiB | C++ |
|
神利·代目 |
100 | 0.090 s | 4.40 MiB | C++ |
|
神利·代目 |
100 | 0.094 s | 4.40 MiB | C++ |
 赵赵赵 |
100 | 0.141 s | 0.18 MiB | Pascal |
|
赵赵赵 |
100 | 0.144 s | 0.18 MiB | Pascal |
|
赵赵赵 |
100 | 0.144 s | 0.18 MiB | Pascal |
|
赵赵赵 |
100 | 0.158 s | 0.16 MiB | Pascal |
| 本题关联比赛 | |||
| 20120323 | |||
| 关于 最大公约数 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
有O(T*n^(0.25))的方法
| ||||
|
裸欧拉函数……
| ||||
|
回复 @Hallmeow : ...
 sasasas
2017-04-03 16:18
9楼
| ||||
|
膜拜大神xyz Orz
 Hallmeow
2017-04-03 16:06
8楼
| ||||
|
看到这题，我居然向着莫比乌斯反演方向走上了不归路。真是欧拉函数的裸题。
| ||||
|
if(!x%i)和if(!(x%i))是不一样的。。get√
| ||||
|
| ||||
|
VIP Ezoi 连榜都上不了强行宣称占领系列233333 Orz LPX
 沉迷学习的假的Keller
2016-09-21 15:47
4楼
| ||||
|
Ezoi 即将占领此题 Orz...LPX
 svideo
2016-09-21 15:22
3楼
| ||||
|
暴力水过
 Sky_miner
2016-09-19 16:20
2楼
| ||||
HZOI_RXR
FoolMike
sxysxy
派特三石【问题描述】
两个正整数 a 和 b 的最大公约数 $\gcd{(a,b)}$ ，有时记为$(a,b)$，是对于 a 、 b 来说最大的共同约数，举例来说，$（ 1 ， 2 ） =1 ，（ 12 ， 18 ） =6 $。
利用欧几里得算法很容易求出$（ a,b ）$，现在 Carp 正在思考一个更复杂的问题：
给定整数 N 和 M ，到底存在多少个 $X$ ，使得其满足条件： $1 ≤ X ≤ N 并且 (X,N) ≥ M$ 。
利用欧几里得算法很容易求出$（ a,b ）$，现在 Carp 正在思考一个更复杂的问题：
给定整数 N 和 M ，到底存在多少个 $X$ ，使得其满足条件： $1 ≤ X ≤ N 并且 (X,N) ≥ M$ 。
【输入格式】
输入文件第一行有一个整数 T （ T ≤ 3000 ），表示测试数据的个数，接下来有 T 行，每行包含两个数 N 和 M ，$1 ≤ N ≤ 1000000000 ， 0 ≤ M ≤ 1000000000 $，表示一组测试数据。
【输出格式】
对于每组测试数据，输出一个结果，每个结果占一行。
【输入样例】
gcd.in
3
1 1
10 2
10000 72
1 1
10 2
10000 72
gcd.out
1
6
260
1
6
260