解一元二次方程的烦恼

GitHub 跳转原题关系图返回列表

逐行提取字符串中的数字形成整数，超过 4e7 直接报大，否则做素数判断并按升序输出质因数分解。

OJ: luogu

题目 ID: P1619

难度:普及-

标签:字符串模拟数论

日期: 2026-06-18 21:50

题意

这题的输入不是一个“正常整数”，而是一行任意字符串。
每次都要先输出 Enter the number=，然后读入一行，把其中所有数字字符按原顺序提取出来，拼成一个十进制整数。

如果这一行里没有任何数字，就直接结束程序。
否则对提取出来的数做判断：

若大于 40000000，输出 Prime? No! 和 The number is too large!
若是素数，输出 Prime? Yes!
若不是素数，输出 Prime? No!
如果它还是一个大于 1 的合数，再输出它的质因数分解

下面这张表最容易帮我们看懂“输入到底怎么解释”：

原字符串	提取后的数字	含义
`1.5`	`15`	按 `15` 处理
`-1`	`1`	按 `1` 处理
`1234###24#@13#@￥！1`	`123424131`	超过上界，直接报大
`halt@@`	空串	结束程序

思路

先看一个最直接的朴素做法：

按题意模拟整套流程：

读入一整行字符串；
提取其中所有数字字符；
如果没有数字，直接结束；
如果得到的数超过 40000000，直接输出过大提示；
否则判断素数；
如果是合数，再按升序输出质因数分解。

cpp

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

string s;

string extract_digits(const string &src) {
    string digits;
    for (char ch : src) {
        if (ch >= '0' && ch <= '9') {
            digits += ch;
        }
    }
    return digits;
}

string normalize_number_string(const string &digits) {
    int pos = 0;
    while (pos < (int) digits.size() && digits[pos] == '0') {
        pos++;
    }
    if (pos == (int) digits.size()) {
        return "0";
    }
    return digits.substr(pos);
}

bool is_too_large(const string &num) {
    const string LIMIT = "40000000";
    if ((int) num.size() > (int) LIMIT.size()) {
        return true;
    }
    if ((int) num.size() < (int) LIMIT.size()) {
        return false;
    }
    return num > LIMIT;
}

int string_to_int(const string &num) {
    int value = 0;
    for (char ch : num) {
        value = value * 10 + (ch - '0');
    }
    return value;
}

// 朴素素性判断：从 2 一直试到 n-1，只适合小数据对拍。
bool is_prime_bruteforce(int n) {
    if (n <= 1) {
        return false;
    }
    for (int d = 2; d < n; d++) {
        if (n % d == 0) {
            return false;
        }
    }
    return true;
}

string factorize_to_string(int n) {
    int x = n;
    string res = to_string(n) + "=";
    bool first = true;

    for (int p = 2; p <= x; p++) {
        if (x % p != 0) {
            continue;
        }
        int cnt = 0;
        while (x % p == 0) {
            x /= p;
            cnt++;
        }
        if (!first) {
            res += "*";
        }
        first = false;
        res += to_string(p) + "^" + to_string(cnt);
    }

    return res;
}

bool solve_one(const string &line) {
    string digits = extract_digits(line);
    if (digits.empty()) {
        return false;
    }

    string num = normalize_number_string(digits);

    if (is_too_large(num)) {
        cout << "Prime? No!\n";
        cout << "The number is too large!\n\n";
        return true;
    }

    int value = string_to_int(num);
    if (is_prime_bruteforce(value)) {
        cout << "Prime? Yes!\n\n";
        return true;
    }

    cout << "Prime? No!\n";
    if (value > 1) {
        cout << factorize_to_string(value) << '\n';
    }
    cout << '\n';
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while (true) {
        cout << "Enter the number=\n";
        if (!getline(cin, s)) {
            break;
        }
        if (!solve_one(s)) {
            break;
        }
    }

    return 0;
}

这题真正容易错的是审题，不是算法。

最关键的两个点是：

结束条件不是某个固定单词，而是“这一行完全提取不到数字”；
像 -1、1.5 这样的输入，都会先做“提取数字”这一步，所以它们分别会被当作 1 和 15。

正式代码只是在朴素模拟的基础上，把几个关键步骤拆成函数：

extract_digits()：提取数字；
normalize_number_string()：去掉前导零；
is_too_large()：先用字符串判断是否超过 40000000；
is_prime()：试除判断素数；
factorize_to_string()：输出质因数分解。

代码

cpp

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132#include <bits/stdc++.h>
using namespace std;

string s;

string extract_digits(const string &src) {
    string digits;
    for (char ch : src) {
        if (ch >= '0' && ch <= '9') {
            digits += ch;
        }
    }
    return digits;
}

string normalize_number_string(const string &digits) {
    int pos = 0;
    while (pos < (int) digits.size() && digits[pos] == '0') {
        pos++;
    }
    if (pos == (int) digits.size()) {
        return "0";
    }
    return digits.substr(pos);
}

bool is_too_large(const string &num) {
    const string LIMIT = "40000000";
    if ((int) num.size() > (int) LIMIT.size()) {
        return true;
    }
    if ((int) num.size() < (int) LIMIT.size()) {
        return false;
    }
    return num > LIMIT;
}

int string_to_int(const string &num) {
    int value = 0;
    for (char ch : num) {
        value = value * 10 + (ch - '0');
    }
    return value;
}

bool is_prime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int d = 2; 1LL * d * d <= n; d++) {
        if (n % d == 0) {
            return false;
        }
    }
    return true;
}

string factorize_to_string(int n) {
    int x = n;
    string res = to_string(n) + "=";
    bool first = true;

    for (int p = 2; 1LL * p * p <= x; p++) {
        if (x % p != 0) {
            continue;
        }
        int cnt = 0;
        while (x % p == 0) {
            x /= p;
            cnt++;
        }
        if (!first) {
            res += "*";
        }
        first = false;
        res += to_string(p) + "^" + to_string(cnt);
    }

    if (x > 1) {
        if (!first) {
            res += "*";
        }
        res += to_string(x) + "^1";
    }

    return res;
}

bool solve_one(const string &line) {
    string digits = extract_digits(line);
    if (digits.empty()) {
        return false;
    }

    string num = normalize_number_string(digits);

    if (is_too_large(num)) {
        cout << "Prime? No!\n";
        cout << "The number is too large!\n\n";
        return true;
    }

    int value = string_to_int(num);
    if (is_prime(value)) {
        cout << "Prime? Yes!\n\n";
        return true;
    }

    cout << "Prime? No!\n";
    if (value > 1) {
        cout << factorize_to_string(value) << '\n';
    }
    cout << '\n';
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while (true) {
        cout << "Enter the number=\n";
        if (!getline(cin, s)) {
            break;
        }
        if (!solve_one(s)) {
            break;
        }
    }

    return 0;
}

复杂度

设提取出的整数为 N，输入行长度为 len。
提取数字的复杂度是 $O(len)$ ，素性判断与质因数分解的复杂度是 $O(\sqrt{N})$ 。
空间复杂度是 $O(len)$ 。

总结

这题是典型的“字符串模拟 + 数论”题。

不要急着看素数判断，先把输入解释规则读清楚：

读整行；
提取数字；
没有数字就结束；
超上界就报大；
否则再做素数判断和分解。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P1619 解一元二次方程的烦恼

题目背景

JosephZheng 在写数学作业的预习。他往往使用 Casio 来帮忙解一元二次方程。但是 Casio 有一个问题，就是当 $\Delta=b^2-4ac$ 为一个大素数或大合数时，其开平方的结果会以小数显示，而不是老师要求的二次根式形式。JosephZheng 很是苦恼，一遇到这种情况就要手动解方程。一天他再也忍不住了，于是打开了电脑，编了一个 prime 程序……于是悲剧的 OIer 们就要跟着疯狂的 JosephZheng 一起编这个程序，呵呵……

题目描述

废话少说，给你一个大数 $N$ （可能大于 $4 \times 10^7$ ），让你进行素性判断，然后分解质因数。当然，初中数学题不可能有大于 $4 \times 10^7$ 的数让你判断素性，因此超过范围的数可以忽略不计。为了让程序更加贴心，JosephZheng 多了一些要求，会在输入输出中给出具体情况。

输入格式

一个大数 $N$ （ $N$ 为非负整数），其中这个数的各个数位之间可以插入各种符号（包括负号和小数点等，它们也需要被忽略），例如 $1234$ 可以为 1 - 2alsdkjf3！@￥%！@@@##￥……！￥#-4 等。你需要在这一长串乱码中找出这个要判断的数。

输入数据可能有多组，如果读到一行没有数字的字串即结束。

保证输入数据不超过 $100$ 组，字符串长度不超过 $1000$ 。

输出格式

在读入数据之前先输出 Enter the number=，需要换行。

然后输出 Prime?，问号后有一个空格，但不要换行。

如果是质数则输出 Yes! 否则输出 No!。此时换行。

若果是质数就 halt，若是小于 $2$ 的数则在输出 No! 后也 halt。

若是合数则分解质因数。如果该数大于 $4 \times 10^7$ 则输出 The number is too large!，然后 halt。

否则分解质因数。

输出结果的方式在输出样例中会详细给出。

每组数据之间空一行。

（halt：停止处理本组数据）

输入输出样例 #1

输入 #1

text

1
24
eed

输出 #1

text

1
2
3
4
5Enter the number=
Prime? No!
4=2^2

Enter the number=

输入输出样例 #2

输入 #2

text

1
22
end

输出 #2

text

1
2
3
4Enter the number=
Prime? Yes!

Enter the number=

输入输出样例 #3

输入 #3

text

1
2-1
adfs

输出 #3

text

1
2
3
4Enter the number=
Prime? No!

Enter the number=

输入输出样例 #4

输入 #4

text

1
21234###24#@13#@￥！1
hehe

输出 #4

text

1
2
3
4
5Enter the number=
Prime? No!
The number is too large!

Enter the number=

输入输出样例 #5

输入 #5

text

1
2
3
41.5
1
1234324123512343123
@~@~@~@

输出 #5

text

1
2
3
4
5
6
7
8
9
10
11
12Enter the number=
Prime? No!
15=3^1*5^1

Enter the number=
Prime? No!

Enter the number=
Prime? No!
The number is too large!

Enter the number=

输入输出样例 #6

输入 #6

text

1
212
halt@@

输出 #6

text

1
2
3
4
5Enter the number=
Prime? No!
12=2^2*3^1

Enter the number=

说明/提示

编这道题的 JosephZheng 有些无聊，但是很考验基本功哦！仔细审题！

水题一道。。。

解一元二次方程的烦恼

目录

题意

思路

代码

复杂度

总结

一图流解析