Description

小明有两个正整数x、y，他想把这两个数的乘积x·y写成另外两个正整数相乘的形式，即选择a、b，使得x·y=a·b。小明想通过选择合适的a、b，使得gcd(a,b)尽可能大，你

需要帮小明找到gcd(a,b)的最大值。小明觉得这个问题太简单了，他还想知道，有多少种选择a、b的方式，使得gcd(a,b)达到最大。

Input Format

Output Format

【样例输入1】
5 8

【样例输入2】
20 4

【样例输出1】
2 4

【样例输出2】
4 2

Hint

【样例解释1】

5·8=40

40=2·20=4·10=10·4=20·2

注意a、b是有序的，所以2·20与20·2是两种不同的方案

【样例解释2】

20·4=80

80=4·20=20·4

注意a=x，b=y是允许的

【数据规模和约定】

对于10%的数据， 1<=x,y<=10^3

对于40%的数据， 1<=x,y<=10^6

对于100%的数据， 1<=x,y<=10^12

#include <iostream>
#include <cmath>
// #define max(a, b) (a)>(b)?(a):(b)
using namespace std;
typedef long long ll;
const int N = 1e6+5;
ll a, b;
int primes[N], c[N], cnt;
void divide_primes(ll x, ll y){
    for(int i=2;i<=sqrt(max(x, y));i++){
        
        if(x%i==0||y%i==0){
            primes[++cnt] = i;
            while(x%i==0){
                c[cnt] ++;
                x/=i;
            }
            while(y%i==0){
                c[cnt] ++;
                y/=i;
            }
        }
    }
    if(x>1){
        primes[++cnt] = x;
        c[cnt] ++;
    }
    if(y>1){
        if(x!=y) {
            primes[++cnt] = y;
        }
        c[cnt] ++;

    }
}
int main(){
    cin>>a>>b;
    divide_primes(a, b);
    unsigned long long g = 1, ans = 1;
    for(int i=1;i<=cnt;i++){
        if(c[i]%2) ans = ans * 2; //次数为奇数时有两种选择
        for(int j=0;j<c[i]/2;j++){
            g = g*primes[i];
        }
    }
    cout<<g<<' '<<ans;
    return 0;
}

Source