首页 > 代码库 > 洛谷 P1029 最大公约数和最小公倍数问题 Label：Water&&非学习区警告
洛谷 P1029 最大公约数和最小公倍数问题 Label：Water&&非学习区警告
题目描述
输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数
条件:
1.P,Q是正整数
2.要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.
输入输出格式
输入格式：
二个正整数x0,y0
输出格式：
一个数，表示求出满足条件的P,Q的个数
输入输出样例
输入样例#1：
3 60
输出样例#1：
4
说明
P,Q有4种
3 60 15 12 12 15 60 3
代码
1 #include<cmath> 2 #include<cstdio> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #define ll long long 7 using namespace std; 8 ll x,y; 9 ll ans;10 11 ll gcd(ll a,ll b){12 if(b==0) return a;13 else return gcd(b,a%b);14 }15 16 int main(){17 // freopen("01.in","r",stdin);18 cin>>x>>y;19 for(ll i=x;i*i<=x*y;i+=x){20 if(double(x)*double(y)/double(i)-x*y/i!=0.0) continue;21 if(gcd(i,x*y/i)==x){22 ans+=2;23 } 24 }25 cout<<ans<<endl;26 }
洛谷 P1029 最大公约数和最小公倍数问题 Label：Water&&非学习区警告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。