一元夺宝网站建设2017,开封网站建设流程与开发步骤,手机高端网站建设,全球十大软件公司[NOIP2001 普及组] 最大公约数和最小公倍数问题
题目描述
输入两个正整数 x 0 , y 0 x_0, y_0 x0,y0#xff0c;求出满足下列条件的 P , Q P, Q P,Q 的个数#xff1a; P , Q P,Q P,Q 是正整数。 要求 P , Q P, Q P,Q 以 x 0 x_0 x0 为最大公约数#xff0c;以…[NOIP2001 普及组] 最大公约数和最小公倍数问题
题目描述
输入两个正整数 x 0 , y 0 x_0, y_0 x0,y0求出满足下列条件的 P , Q P, Q P,Q 的个数 P , Q P,Q P,Q 是正整数。 要求 P , Q P, Q P,Q 以 x 0 x_0 x0 为最大公约数以 y 0 y_0 y0 为最小公倍数。
试求满足条件的所有可能的 P , Q P, Q P,Q 的个数。
输入格式
一行两个正整数 x 0 , y 0 x_0, y_0 x0,y0。
输出格式
一行一个数表示求出满足条件的 P , Q P, Q P,Q 的个数。
样例 #1
样例输入 #1
3 60样例输出 #1
4提示 P , Q P,Q P,Q 有 4 4 4 种 3 , 60 3, 60 3,60。 15 , 12 15, 12 15,12。 12 , 15 12, 15 12,15。 60 , 3 60, 3 60,3。
对于 100 % 100\% 100% 的数据 2 ≤ x 0 , y 0 ≤ 10 5 2 \le x_0, y_0 \le {10}^5 2≤x0,y0≤105。
【题目来源】
NOIP 2001 普及组第二题 思路
gcd(p, q) * lcm(p, q) p * q AC代码
#include iostream
#define AUTHOR HEX9CF
using namespace std;int gcd(int x, int y) {int r;if(x y) {x ^ y ^ x ^ y;}r x % y;if(!r) {return y;}return gcd(y, r);
}int main()
{int x, y;int cnt 0;cin x y;for (int p x; p y; p){int q x * y / p;int g gcd(p, q);if (g x p * q / g y){// cout p q endl;cnt;}}cout cnt endl;return 0;
}
