第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-681 最大公约数和最小公倍数问题

#include<stdio.h>
int isprime(int m,int n)
{
	int t;
	while(m%n!=0)
	{
		t=m%n;
		m=n;
		n=t;
	}
	return n;
}
int main()
{
	int x,y;
	int num=0;
	scanf("%d %d",&x,&y);
	int i,j;
	long long int s;
	long long int t;
	s=x*y;
	for(i=x;i<=y;i++)
	{
		if(s%i==0)
		{
			t=isprime(i,s/i);
			if(t==x&&s/t==y)
			{
				num++;
			}
		}
	}
	printf("%d",num);
	return 0;
} 

#include<bits/stdc++.h>
using namespace std;
int f(int a,int b){
	if(b==0)
	return a;
	else 
	return f(b,a%b);
}
int main(){
	int x,y,k,sum=0;
	cin>>x>>y;
	if(x>y){
		for(int i=y;i<=x;i++){
			if(f(i,x*y/i)==y&&x*y%i==0)
			sum++;
		}
	}else{
		for(int i=x;i<=y;i++){
			if(f(i,x*y/i)==x&&x*y%i==0)
			sum++;
		}
	}
	cout<<sum<<endl;
	return 0;
}

import java.util.Scanner;

public class Main {

    private static int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a, b;
        a = scanner.nextInt(); // x0
        b = scanner.nextInt(); // y0
        int count = 0;
        // 由于“最大公约数和最小公倍数的乘积就是原两个数的积”，所以有条件 x0 <= P, Q <= x0 * y0
        for (int i = a; i * i <= a * b; i += a) { // i+=a 是一种优化，i++ 也可行
            if (((a * b) % i == 0) && // 首先 i 要满足是 x0 * y0 的约数
                gcd(i, (a * b) / i) == a) { // 其次 i, (x0 * y0) / i 以 x0 为最大公约数，自然满足 i * ((x0 * y0) / i) / gcd(i, (x0 * y0) / i) = y0
                count += 2; // i, (x0 * y0) / i 和 (x0 * y0) / i, i 都是满足条件的 P、Q
            }
        }
        System.out.println(count);
    }
}

x0, y0 = map(int, input().split())


def gcd(x, y):  # 最大公约数
    if x < y:
        x, y = y, x
    r = x % y  # x是大数 y是小数 24%15
    while r != 0:
        x = y
        y = r
        r = x % y
    return y


def lcm(x, y):  # 最小公倍数 x是大数 y是小数
    if x < y:
        x, y = y, x
    m = x
    while x % y != 0:
        x = x+m
    return x


n = x0 * y0  
ans = 0
for i in range(x0,y0+1):  # x×y=P×Q, gcd(x,y)=P ,lcm(x,y)=Q 
    if n % i == 0 and gcd(i, n // i) == x0 and lcm(i, n // i) == y0: 
        ans += 1
print(ans)