(数论 最大公约数 最小公倍数) codeVs 1012 最大公约数和最小公倍数问题

题目描述  Description

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

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

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

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

输入描述  Input Description

二个正整数x0,y0

输出描述  Output Description

满足条件的所有可能的两个正整数的个数

样例输入  Sample Input

3 60

样例输出  Sample Output

4

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

审题。。。。。注意要得到所有符合条件的个数中，第一个数并不一定比第二个数大。其中，一般来说这两个数的最小一定为最大公约数，最大数一定为最小公倍数。

C++代码：

#include<iostream> #include<cmath> using namespace std; int fun1(int a,int b){ int tmp; while(b){ tmp = b; b = a%b; a = tmp; } return a; } int fun2(int a,int b){ return a/fun1(a,b)*b; } int main(){ int x,y; cin>>x>>y; int m = x*y; int sum = 0; for(int i = x; i <= y; i++){ int j = m/i; if(j*i != m) continue; else{ if(fun1(i,j) == x && fun2(i,j) == y){ sum++; } } } cout<<sum<<endl; return 0; }

 

转载于:https://www.cnblogs.com/Weixu-Liu/p/10630328.html