[题解][CSP.AC:125] - 【冬令营】Day3T2-数分解

题目描述

【问题描述】

小明有两个正整数 $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\leq x,y\leq 10^3$

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

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

算法

思路

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

根据算数基本定理,

\begin{aligned} 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{aligned}

所以,

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\leq x,y \leq 10^{12}$ , 会爆 int, 我被这个坑了很久, 直到调试的时候看到负数.

代码实现

cpp

#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;
}

[题解][CSP.AC:125] - 【冬令营】Day3T2-数分解

题目描述

【问题描述】

【输入格式】

【输出格式】

【样例输入1】

【样例输出1】

【样例解释1】

【样例输入2】

【样例输出2】

【样例解释2】

【数据规模和约定】

算法

思路

代码实现

题目链接

讨论

题目描述 ​

【问题描述】 ​

【输入格式】 ​

【输出格式】 ​

【样例输入1】 ​

【样例输出1】 ​

【样例解释1】 ​

【样例输入2】 ​

【样例输出2】 ​

【样例解释2】 ​

【数据规模和约定】 ​

算法 ​

思路 ​

代码实现 ​

题目链接 ​

讨论

题目描述

【问题描述】

【输入格式】

【输出格式】

【样例输入1】

【样例输出1】

【样例解释1】

【样例输入2】

【样例输出2】

【样例解释2】

【数据规模和约定】

算法

思路

代码实现

题目链接