2018年信息学奥赛NOIP资料下载 题目描述 输入22个正整数x_0,y_0(2 \le x_0<100000,2 \le y_0<=1000000)x 0 ,y 0 (2≤x 0 <100000,2≤y 0 <=1000000),求出满足下列条件的P,QP,Q的个数
条件:
P,QP,Q是正整数
要求P,QP,Q以x_0x 0 为最大公约数,以y_0y 0 为最小公倍数.
试求:满足条件的所有可能的22个正整数的个数.
输入输出格式 输入格式： 22个正整数x_0,y_0x 0 ,y 0 输出格式： 11个数，表示求出满足条件的P,QP,Q的个数
输入输出样例 输入样例#1： 3 60 输出样例#1： 4 说明 P,QP,Q有4种
1、3,60 2、15,12 3、12,15 4、60,3
#include<iostream> #include<cmath> using namespace std; int gcd(int a,int b)//求最大公约数 { while(b!=0)//辗转相除法求最大公约数 { int qwq=a%b; a=b; b=qwq; } return a; //return b == 0 ? a : gcd(b,a%b); } int main() { int x,y; cin>>x>>y;//输入最大公约数以及最小公倍数 int v=x*y;//最大值 int s=(int)sqrt(v);//不用重复进行寻找 int n=0; for(int i=x;i<=s;i++) if((v%i==0)//如果最大值能够整除当前的数，则说明找到了一组可能是真的的解 &&(gcd(v/i,i)==x))//如果另外一个数与当前的数的最大公约数等于输入的最大公约数 n++;//进行计数 cout<<n*2;// 不进行重复的筛之后要加上另一块的 return 0; }