Codeforces1062B. Math（合数分解）

题目链接：传送门

题目：

B. Math
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

JATC's math teacher always gives the class some interesting math problems so that they don't get bored. Today the problem is as follows. Given an integer n

, you can perform the following operations zero or more times:

    mul x

: multiplies n by x (where x
is an arbitrary positive integer).
sqrt: replaces n
with n−−√ (to apply this operation, n−−√

    must be an integer). 

You can perform these operations as many times as you like. What is the minimum value of n

, that can be achieved and what is the minimum number of operations, to achieve that minimum value?

Apparently, no one in the class knows the answer to this problem, maybe you can help them?
Input

The only line of the input contains a single integer n
(1≤n≤106

) — the initial number.
Output

Print two integers: the minimum integer n

that can be achieved using the described operations and the minimum number of operations required.
Examples
Input
Copy

20

Output
Copy

10 2

Input
Copy

5184

Output
Copy

6 4

Note

In the first example, you can apply the operation mul 5
to get 100 and then sqrt to get 10

.

In the second example, you can first apply sqrt to get 72
, then mul 18 to get 1296 and finally two more sqrt and you get 6

.

Note, that even if the initial value of n
is less or equal 106, it can still become greater than 106 after applying one or more operations.

View Code

题目大意：

　　输入一个数n，对这个数可以进行两种操作：

　　（1）乘上一个任意大小的整数；

　　（2）取平方根。（这里要求取平方根前必须为完全平方数）

　　问使得输入的n经过任意次操作变成最小值时，输出这个最小值和变成最小值所需要的最少的操作数。

　　1 ≤ n ≤ 10⁶。

思路：

　　①：n的最小值为它所有质因子的乘积；（如果有一个质因子的指数大于1，那么就不是最小的，而且通过操作②③变成最小的）

　　②：操作（1）最多只需要执行一次，用这次操作把n所有质因子的指数都变成相同的，并且这个指数的值为2的幂次（取平方根时幂次会/=2）；

　　③：操作（2）的次数就是②步骤结束后，log₂（质因子的指数）。

然后把②和③的次数合起来就好了。

实现：

　　试除法筛出n所有的质因子p_i及其指数c_i，则第一个答案a = $prod_{i=1}^{fatCnt}p_{i}$。（fatCnt为质因子的数量）

　　令b = max(c_i)，令2^t为最小的不小于b的2的幂次。

　　①：如果t为0，那么答案为0；（n不可能变得更小了）

　　②：只要有一个c_i < 2^t，答案就为t+1；（必须要执行一次操作（1），才能不断的开方）

　　③：如果所有的c_i = 2^t，答案为t。（此时不执行操作（1），就可以不断开方直到最小）

代码：

　　（马上去补！）

比赛代码：

#include <bits/stdc++.h>

using namespace std;
const int MAX_N = 10000;
int prime[MAX_N+1];
void getPrime()
{
    memset(prime, 0, sizeof prime);
    for (int i = 2; i <= MAX_N; i++) {
        if (!prime[i]) prime[++prime[0]] = i;
        for (int j = 1; j <= prime[0] && prime[j] <= MAX_N/i; j++) {
            prime[prime[j]*i] = 1;
            if (i%prime[j] == 0) break;
        }
    }
}

int factor[100][2];
int fatCnt;
int getFactors(int x)
{
    fatCnt = 0;
    int tmp = x;
    for (int i = 1; prime[i] <= tmp/prime[i]; i++) {
        if (tmp % prime[i] == 0) {
            factor[fatCnt][0] = prime[i];
            factor[fatCnt][1] = 0;
            while (tmp % prime[i] == 0) {
                factor[fatCnt][1]++;
                tmp /= prime[i];
            }
            fatCnt++;
        }
    }
    if (tmp > 1) {
        factor[fatCnt][0] = tmp;
        factor[fatCnt][1] = 1;
        fatCnt++;
    }
    return fatCnt;
}

int getbin(int x)
{
    int tmp = 1;
    while (tmp < x) {
        tmp <<= 1;
    }
    return tmp;
}

bool check(int ansb)
{//ÊÇ·ñÓÐ²»Í¬
    int cnt = factor[0][1];
    if (cnt != (1<<ansb))
        return true;
    for (int i = 0; i < fatCnt; i++) {
        if (factor[i][1] != cnt)
            return true;
    }
    return false;
}

//int bin[21];
int main() {
//    bin[0] = 1;
//    for (int i = 1; i < 21; i++) bin[i] = bin[i-1] << 1;
    getPrime();
    int N;
    cin >> N;
    getFactors((int)N);
    int a = 1, b = 0;
    for (int i = 0; i < fatCnt; i++) {
        a *= factor[i][0];
        b = max(b, getbin(factor[i][1]));
    }
    int ansb = 0;
    while (b > 1) {
        ansb++;
        b >>= 1;
    }
    if (ansb > 0 && check(ansb)) {
        ansb++;
    }
    cout << a << ' ' << ansb << endl;
    return 0;
}

View Code