题目描述

【问题描述】

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

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

【输入格式】

一行两个正整数$x、y$

【输出格式】

输出两个数, 用一个空格隔开。第一个数表示$gcd(a,b)$的最大值, 第二个数表示使得$gcd(a,b)$达到最大的方案数。

【样例输入1】

5 8

【样例输出1】

2 4

【样例解释1】

$5·8=40$

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

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

【样例输入2】

20 4

【样例输出2】

4 2

【样例解释2】

$20·4=80$

$80=4·20=20·4$

注意$a=x,b=y$是允许的

【数据规模和约定】

对于10%的数据, $1\le x,y\le {10}^3$

对于40%的数据, $1\le x,y\le {10}^6$

对于100%的数据, $1\le x,y\le {10}^{12}$

---

算法

思路

首先, $gcd(a,b)$ 是 $a,b$ 的最大公约数, 那么在 $a\cdot b$ 一定时, 如何使 $gcd(a,b)$ 最大呢?

根据算数基本定理,

$$\begin{array}{rl}x& =p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}{p}_3^{{\alpha }_3}{p}_4^{{\alpha }_4}\dots p_n^{{\alpha }_n}\\ \\ y& =p_1^{{\beta }_1}{p}_2^{{\beta }_2}{p}_3^{{\beta }_3}{p}_4^{{\beta }_4}\dots p_n^{{\beta }_n}\end{array}$$

所以,

$$a\cdot b=p_1^{{\alpha }_1+{\beta }_1}{p}_2^{{\alpha }_2+{\beta }_2}{p}_3^{{\alpha }_3+{\beta }_3}{p}_4^{{\alpha }_4+{\beta }_4}\dots p_n^{{\alpha }_n+{\beta }_n}$$

很明显, $gcd(a,b)$ 最大时, 对于 $a\cdot b$ 的每个质因子, 它的指数一定被平分给 $a,b$, 而由于 $a,b$ 都为整数, 所以当一个质因子指数为奇数时, 会出现两种可能的情况, 根据乘法原理, 情况数要乘以二.

$$gcd(a,b{)}_{\text{max}}=p_1^{\lfloor \frac{{\alpha }_1+{\beta }_1}{2}\rfloor }{p}_2^{\lfloor \frac{{\alpha }_2+{\beta }_2}{2}\rfloor }{p}_3^{\lfloor \frac{{\alpha }_3+{\beta }_3}{2}\rfloor }{p}_4^{\lfloor \frac{{\alpha }_4+{\beta }_4}{2}\rfloor }\dots p_n^{\lfloor \frac{{\alpha }_n+{\beta }_n}{2}\rfloor }$$

最后, 绝对绝对不能忘记该题的数据范围, $1\le x,y\le {10}^{12}$, 会爆 int, 我被这个坑了很久, 直到调试的时候看到负数.

代码实现

#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;
ll primes[N], c[N], cnt;

void divide_primes(ll x, ll y){ //分解质因数
    for(int i=2;i<=max(x, y)/i;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;
}

题目链接