题目描述

【问题描述】

小明有两个正整数、, 他想把这两个数的乘积写成另外两个正整数相乘的形式, 即选择、, 使得。小明想通过选择合适的、, 使得尽可能大, 你

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

【输入格式】

一行两个正整数、

【输出格式】

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

【样例输入1】

1
5 8

【样例输出1】

1
2 4

【样例解释1】

注意、是有序的, 所以与是两种不同的方案

【样例输入2】

1
20 4

【样例输出2】

1
4 2

【样例解释2】

注意是允许的

【数据规模和约定】

对于10%的数据,

对于40%的数据,

对于100%的数据,

算法

思路

首先, 是 的最大公约数, 那么在 一定时, 如何使 最大呢?

根据算数基本定理,

所以,

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

最后, 绝对绝对不能忘记该题的数据范围, , 会爆 int, 我被这个坑了很久, 直到调试的时候看到负数.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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;
}

题目链接