题解 P1619 【解一元二次方程的烦恼】

_neddy · 2019-05-13 20:46:00 · 题解

~~这题其实挺简单的。前后才交了六次而已。~~

方法很简单。

但在解决问题之前，先分析一下时间复杂度：

判断素数最坏情况是O(sqrt(n))的
提取数字是O(1)的
分解质因数是O(sqrt(n))的

这样算下来，设有Q次询问，则时间复杂度为O(Q sqrt(n))，不算是个很优秀的复杂度。如果数据加强至

Q<=100000, n <=40000000

则现有的所有解法都会GG，此时则需运用到各种筛法并保存质因数，可惜作者太蒻了只会口胡。

回到正题，来解决这道数据水到爆炸的题目：

读题，易知判断素数和质因数分解为题目的主要考点（废话

那么，我们需要写个判断素数的函数，和分解质因数的函数。题目说输入中有干扰字符，且大于四千万的数都过滤掉，这时可用string读入，再提取数字。

提取数字的部分很简单（~~其实这整道题都很简单~~

inline int str_to_int64(string ss)
{
    int num = 0, flag = 0;
    for (register int i = 0; i < ss.size() && num <= 40000000; ++i) //大于40000000的数过滤掉
        if (ss[i] >= '0' && ss[i] <= '9') num = num * 10 + (ss[i] - '0'), flag = 1;
    if (flag == 0) exit(0); //串中没有一个数字，halt
    return num;
}

坑点主要在于素数判断之后的输出以及质因数分解。即使你在isprime中写

if (n < 2) return 0;

判断时输入一个0还是会崩，然而我没有注意到时却过了，再次说明数据之水。

所以，应该在判断和分解的部分中再加入判断：

inline void act(int n){
    int num = 0, sum = 0, flag = 0, Isprime = isprime(n); //提前保存好值，避免重复计算
    n <= 40000000 && Isprime ? cout << "Prime? Yes!\n\n" : cout << "Prime? No!\n"; //如果满足既小于等于40000000又是素数则输出Yes，否则输出No
    if (Isprime || n < 2 || n > 40000000) {
        if (n > 40000000) cout << "The number is too large!\n\n"; //数字过大
        if (n < 2) cout << '\n'; //数字过小
        return ;
    }
    cout << n << '='; //质因数分解
    for (register int i = 2; i * i <= n; ++i){
        while(n % i == 0) n /= i, ++sum;
        if (sum)
            if (flag) cout << '*' << i << '^' << sum, sum = 0; //不是第一个，输出乘号
            else cout << i << '^' << sum, flag = true, sum = 0; //是第一个，不输出
    }
    Isprime ? cout << '*' << n << "^1\n\n" : cout << "\n\n"; //如果分解之后的剩下的数是一个素数则加进去，否则开始下一次
}

差不多就这样了吧。完整代码如下：

#include <bits/stdc++.h> //注释如上，不再添加重复部分

using namespace std;

inline bool isprime(int n){
    for (register int i = 2; i * i <= n; ++i) if (n % i == 0) return 0;
    return !(n < 2); //这不是一个好的写法，但因为数据水就算了
}

inline void act(int n){
    int num = 0, sum = 0, flag = 0, Isprime = isprime(n);
    n <= 40000000 && Isprime ? cout << "Prime? Yes!\n\n" : cout << "Prime? No!\n";
    if (Isprime || n < 2 || n > 40000000) {
        if (n > 40000000) cout << "The number is too large!\n\n";
        if (n < 2) cout << '\n';
        return ;
    }
    cout << n << '=';
    for (register int i = 2; i * i <= n; ++i){
        while(n % i == 0) n /= i, ++sum;
        if (sum)
            if (flag) cout << '*' << i << '^' << sum, sum = 0;
            else cout << i << '^' << sum, flag = true, sum = 0;
    }
    Isprime ? cout << '*' << n << "^1\n\n" : cout << "\n\n";
}

inline int str_to_int64(string ss)
{
    int num = 0, flag = 0;
    for (register int i = 0; i < ss.size() && num <= 40000000; ++i)
        if (ss[i] >= '0' && ss[i] <= '9') num = num * 10 + (ss[i] - '0'), flag = 1;
    if (flag == 0) exit(0);
    return num;
}

int main(){
    string s;
    while(cout << "Enter the number=\n"){ //程序没有终止，持续输出提示
        getline(cin, s); //行末有空格，要用getline
        act(str_to_int64(s)); //开始新一轮
    }
}

这篇题解改了两次，每一次重写我都能发现新的Bug，也正说明了我的能力仍然十分有限。现在的这一篇中，功能基本齐全，且代码较为精简。蒟蒻也不懂什么面向对象，只能用常规方法解决。也欢迎看到题解的dalao前来hack，蒟蒻感激不尽。

总而言之，要解决这道题需要注意以下几点：

如果大于四千万就直接输出不是素数和超范围提示
如果小于四千万，则判断是否素数，如果是就进行下一轮，否则进行分解
如果输入的字符串里没有一个数字，则强制退出
每完成一个数的计算与判断都要额外地空一行！！

最后，祝大家早日AC！