C++ 中的多可整除数

2025 年 5 月 21 日 | 阅读 4 分钟

在本文中，我们将讨论 C++ 中的多可整除数及其算法、伪代码和示例。

C++ 中的多可整除数是什么？

如果一个数的某些前缀满足特定的可整除性要求，则称该数为多可整除数。一个具有 k 位数字的整数 N 的第一位必须能被 1 整除，前两位能被 2 整除，前三位能被 3 整除，依此类推。例如，123 是一个多可整除数，因为 1÷1=1，12÷2=6，123÷3=41。通过反复提取一个数的前缀并确认它们能被其长度整除，我们可以在 C++ 中进行检查。

如果一个数的每个前缀都满足一个特殊的可整除性属性，则该数被认为是多可整除数。当一个数是多可整除数时，会发生以下情况：

第一个数字，即最高位，可被 1 整除。
前两个数字相加可被 2 整除。
前三个数字相加可被 3 整除。
该过程一直持续到整个数字被确认。

换句话说，对于一个数字 N，其数字为 d1, d2,..., dk，由前 i 位数字构成的前缀，对于 i=1,2,...,k，Pi = d1 d2...di 必须能被 i 整除。

例如

1: 1÷1=1 (有效)。

12: 1÷1=1, 12÷2=6 (有效)。

123: 1÷1=1, 12÷2=6, 123÷3=41 (有效)。

1234: 1÷1=1, 12÷2=6, 123÷3=4, 1234÷4=308.5 (无效)。

====

输入: N=768

输出: 768 是一个多可整除数。

例如，如果 p>1 且 p<=数字中的位数，则每个 p 位数字都能被 p 整除。

输入 42587

输出: 没有等于 42587 的多可整除整数。

解释是 p=3 不是一个多可整除数，因为它不满足必要的条件。使用该数字的前三位，425 是一个不能被 3 整除的数字。

算法

给定数字 N 的所有数字都将被移除并存储。
为了存储每个数字，我们将使用一个数组。使用模函数，我们将提取数字并将每个数字除以 10。
由于数组中存储的数字将是反向的，我们将使用 reverse() 函数来翻转数组。
通过循环遍历检查每个 p 位数字是否可被 p 整除。如果对所有 p 值（直到 p 等于给定数字中的位数）都成立，则该数字被认为是多可整除数。
现在，我们将使用 for 循环来确定该数字是否是多可整除数。

伪代码

function isPolydivisible(number)
    convert number to string numStr
    set length to size of numStr
    for i from1 to length do
        set prefix to the first i characters of numStr, converted to integer
        if prefix mod i ≠ 0 then
            return false
        end if
    end for
    return true
end function
main
    input number
    call isPolydivisible(number) and store result
    if result is true then
        print "The number is polydivisible."
    else
        print "The number is not polydivisible."
    end if
end main   

示例

让我们举一个例子来说明 C++ 中的多可整除数。

#include <iostream>
#include <string>
using namespace std;
// Function to check if a number is polydivisible
bool isPolydivisible(long long number) {
    string numStr = to_string(number);
    int length = numStr.size();
    for (int i = 1; i <= length; ++i) {
        // Extract the prefix of length i
        long long prefix = stoll(numStr.substr(0, i));
        // Check if the prefix is divisible by i
        if (prefix % i != 0) {
            return false; // Not polydivisible
        }
    }
    return true; // Polydivisible
}
int main() {
    long long number;
    cout << "Enter a number to check if it is polydivisible: ";
    cin >> number;
    if (isPolydivisible(number)) {
        cout << number << " is a polydivisible number." << endl;
    } else {
        cout << number << " is not a polydivisible number." << endl;
    }

    return 0;
}   

输出

Enter a number to check if it is polydivisible: 34
34 is a polydivisible number.
Enter a number to check if it is polydivisible: 42587
42587 is not a polydivisible number.

说明

输入转换: 为了简化前缀提取，整数被转换为字符串。
前缀提取: 前缀提取是使用 substr 提取长度递增的前缀的过程。
可整除性检查: 每个前缀被转换回整数后，将其长度与其可整除性进行比较。
结果: 如果每个前缀都满足可整除性标准，则该数字是多可整除数。

结论

总之，多可整除数是一个有趣的数学概念，它结合了数字结构和可整除性知识。这些数字为数学分析和编程带来了独特的挑战，提供了一个有趣的机会来研究基于前缀的可整除性定律。通过迭代一个数字的前缀并验证可整除性要求，可以轻松地使用 C++ 确定一个数字的多可整除性。除了展示编程如何用于解决数学问题外，这个概念还拓宽了我们对数字属性和可整除性限制的理解。研究此类主题有助于培养算法解决问题的能力和逻辑推理。

下一主题检查 C++ 中有效 IMEI 号码的程序

C++ 中的多可整除数