top1编程
← 返回题目
题解

最大公约数和最小公倍数问题

2 条题解

  • 0
    @ 2026-7-29 20:23:36
    #include <bits/stdc++.h>
    using namespace std;
    int gcd(int a,int b){
    	//要保证大的数除于小的数
    	if(b>a){
    		swap(a,b);
    	} 
    	//循环重复除法计算,直到b为0
    	while(b!=0){
    		int r;
    		r=a%b;
    		a=b;
    		b=r;
    	} 
    	return a;//返回最大公约数 
    }
    int main(){
    	//x是最大公约数  y是最小公倍数  
    	//3 60
    	//15 12
    	int x,y;
    	cin>>x>>y;
    	int sum=0;
    	//外层循环,遍历区间[x,y]中的每一个值 i (作为这个数对中的较大的数) 
    	for(int i=x;i<=y;i++){
    		//内层循环,遍历区间[x,i-1]中的每一个值 j (作为这个数对中的较小的数) 
    		for(int j=x;j<=i-1;j++){
    			//判断每一个方案的 i 跟  j 
    			//最大公约数是否为x 
    			int g=gcd(i,j);
    			if(g==x && i*j/g==y){
    				//cout<<i<<"  "<<j<<endl;
    				sum++;//满足条件,计数加一 
    			}
    		}
    	}
    	cout<<sum*2;
    	return 0;
    }
    
    • 0
      @ 2026-7-29 1:15:59
      #include <bits/stdc++.h>
      using namespace std;
      int main(){
      	int x,y,s=0;
      	while(cin>>x>>y){
      		for(int i=x;i<=y;i++){//循环有可能的最大公约数范围
      			for(int j=i+1;j<=y;j++){//不重复循环
      			//如果最大公约数等于等于x,最小公倍数是y
      				if(__gcd(i,j)==x&&i/__gcd(i,j)*j==y){
      					s++;//统计正整数的个数
      				}
      			}
      		}
      		cout<<s*2;//正反组合算不同的组合
      	}
      	return 0;
      }
      
      • 1