题解 P4446 【[AHOI2018初中组]根式化简】

· · 题解

一道比较不错的数学思维题 。

本篇题解中可能有一些说的不太严谨的地方，望谅解，可以在评论区提出。

题目大意:

给出 n 个数，对于每一个数x，将其化简为a\sqrt[3]{b}的形式（其中 a 和 b 均为正整数），要求 a 最大，并输出 a 的值

很良心的题面中提到了:

"如果你没有学过这部分数学知识，你可以认为题意是：给你n 个正整数x，对于每一个 x ，你需要求出整数a, b 使得a ^ 3×b=x，输出最大的整数 a 即可。"

在这个式子中，我们不难发现 a 和 b 都是 x 的约数， 所以我们可以发现 a 和 b 不可能同时大于 \sqrt[4]{x},所以我们先将 x 在 \sqrt[4]{x} 的全部约数分离出来，之后我们会发现分离出这些因子后的 x 只有如下两种情况：

1.它是一个完全立方数

2.它不可化简为题面中的形式（不考虑可以化简为p * \sqrt[3]{1} 的这种情况，因为他不会对答案产生任何贡献，也没有任何的化简意义）

证明如下：

如果此时的 x 不但不是一个完全平方数，还可以化简为题面中的形式，那么它一定可以表示为q * p ^ 3（其中 q 和p 均不等于 1）的形式，因为我们已经筛去了在\sqrt[4]{x} 以内的全部约数（此处的 x 为还没有筛去一些因子的 x），所以 p 和 q一定都大于原始的 x 的四分之一次方，此时 q * p ^ 3 一定大于最原来的 x ，这种情况显然是不存在的。

所以我们在分离出小于等于\sqrt[4]{x} 的全部约数之后只需要二分一下它是不是完全立方数即可。

如果还有什么还有什么不懂的地方可以再结合代码里的注释理解一下。

代码如下:

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int maxn = 1000005; 
const int maxm = 31635;

int n, cnt;
int ans, tot;

int prime[maxm];

long long x;

long long p[maxn];

bool check[maxm];

long long read(void)
{
    long long s = 0, w = 1;
    char ch = getchar();
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') w = -1;
    for(; ch <= '9' && ch >= '0'; ch = getchar()) s = s * 10 + ch - '0';
    return s * w;
}

void Euler(int num) // 线性筛素数 
{
    check[1] = true;
    for(int i = 2; i <= num; i++) 
    {
        if(!check[i]) prime[++cnt] = i;
        for(int j = 1; j <= cnt && i * prime[j] <= num; j++)
        {
            check[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

int main()
{
    n = read();
    for(register int i = 1; i <= maxn - 5; i++) p[i] = 1ll * i * i * i; // 完全立方数的预处理 
    Euler(maxm - 3); // 线性筛素数 
    for(; n; n--)
    {
        x = read();
        ans = 1;
        for(int i = 1; i <= cnt && prime[i] <= x; i++) // 枚举小于等于 x 的四分之一次方的素数来去除部分因子 
        {
            for(; x % prime[i] == 0; )
            {
                x /= prime[i];
                tot++;
                if(tot == 3) // 如果这个因子的指数达到了 3 那么他可以对答案产生贡献 
                {
                    ans *= prime[i]; //算上这部分贡献 
                    tot = 0; // 复原指数 
                }
            }
            tot = 0; // 复原指数 
        }
        int pos = lower_bound(p + 1, p + maxn - 4, x) - p; // 二分查找小于等于它的最大的完全平方数 
        if(p[pos] == x) cout << ans * pos << '\n'; // 如果等于，即此时的 x 为一个完全平方数， 要加上它开立方后的贡献 
        else cout << ans << '\n'; // 否则没有贡献 
    }
    return 0;
}

如果有什么疑问的话直接在评论区发或者洛谷私信均可。

谢谢阅读。