题目名称 1417. [NOIP 2001]最大公约数和最小公倍数问题
输入输出 gcdpro.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试数据 10
题目来源 Gravatar铁策 于2013-11-04加入
开放分组 全部用户
提交状态
分类标签
数论 基本
分享题解
通过:231, 提交:702, 通过率:32.91%
GravatarAAAAAAAAAA 100 0.000 s 0.00 MiB C++
GravatarYoungsc 100 0.000 s 0.00 MiB C++
GravatarShallowDream雨梨 100 0.000 s 0.00 MiB C++
GravatarLGLJ 100 0.000 s 0.00 MiB C++
Gravatarzhengtn03 100 0.000 s 0.00 MiB C++
Gravatarw_w 100 0.000 s 0.00 MiB C++
Gravatarlihaoze 100 0.000 s 0.00 MiB C++
Gravatar┭┮﹏┭┮ 100 0.000 s 0.00 MiB C++
GravatarHzoi_chairman 100 0.000 s 0.03 MiB C++
Gravatar金身人面兽 100 0.000 s 0.03 MiB C++
关于 最大公约数和最小公倍数问题 的近10条评论(全部评论)
我的数学是真的烂
Gravatar┭┮﹏┭┮
2023-11-22 19:55 20楼
#include <bits/stdc++.h>
using namespace std;
int gcd (int a,int b) {
if (b == 0) {
return a;
} else {
return gcd(b,a % b);
}
}
long long x,cnt,y;
int main () {
freopen ("gcdpro.in","r",stdin);
freopen ("gcdpro.out","w",stdout);
cin >> x >> y;
for(int i = x; i <= y; i += x) {
long long a = x * y / (1LL * i);
long long c = (a * i) / gcd(a,i);
if (gcd(a,i) == x && c == y) {
cnt++;
}
Gravatar李星昊
2022-10-15 09:47 19楼
数学优化?
Gravatarsnake
2017-11-04 14:13 18楼
为什么输入可以有1
GravatarCSU_Turkey
2017-07-22 13:46 17楼
写个水题能wa三遍我真是!@#¥%……&*()——
GravatarJustWB
2017-04-18 18:27 16楼
回复 @RE:从零开始 :
嗯,有道理。。。
Gravatarliu_runda
2017-01-07 09:00 15楼
回复 @liu_runda :
不就是两数相等吗
GravatarTbnlkegc
2017-01-06 15:46 14楼
第七个测试点,,我也只能

if(X0 == Y0) ans++;

。。。不要怪我=_=````````
GravatarSky_miner
2016-03-28 17:06 13楼
第7个测试点好奇怪,两数的最大公约数和最小公倍数是同一个偶数
Gravatarliu_runda
2015-09-29 11:29 12楼
超时。。。。。
Gravatar进击的小胖
2015-08-29 14:40 11楼

1417. [NOIP 2001]最大公约数和最小公倍数问题

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

【题目描述】

输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数

条件:  1.P,Q是正整数

     2.要求P,Q以x0为最大公约数,以y0为最小公倍数.

试求:满足条件的所有可能的两个正整数的个数.

【输入格式】

输入共一行,二个正整数x0,y0。

【输出格式】

输出共一行,即满足条件的所有可能的两个正整数的个数。

【样例输入】

3 60

【样例输出】

4

【提示】

(不用输出)此时的 P Q 分别为:

3 60

15 12

12 15

60 3

所以,满足条件的所有可能的两个正整数的个数共4种。

【来源】

NOIP2001普及组第二题