大整数的因子

题目描述

给出一个位数不超过 30 的十进制非负整数 $c$ ，求所有满足 $2 \le k \le 9$ 且 $c \bmod k = 0$ 的 $k$ 。若存在，按从小到大输出，相邻两数用一个空格隔开；若不存在，输出 none。样例输入 30，输出 2 3 5 6。

思路

$c$ 有 30 位，普通整数存不下，所以按字符串从高位到低位逐位扫描，对每个 $k$ 维护余数 $r \leftarrow (10r + d) \bmod k$ ；扫完若 $r=0$ 说明 $c$ 能被 $k$ 整除。 $k$ 只有 2 到 9 共 8 个，每个单独扫一遍即可，时间复杂度 $O(8|c|)$ 。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 21:51
# update_at: 2026-10-04 14:44

import sys
from functools import reduce


def mod_by(s: str, k: int) -> int:
    """十进制字符串 s 表示的大整数对 k 取模，逐位递推：r = (r*10 + d) % k。"""
    return reduce(lambda r, ch: (r * 10 + int(ch)) % k, s, 0)


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    c = next(data).decode()  # 大整数按十进制字符串读入，mod_by 要逐位取模
    ans = [str(k) for k in range(2, 10) if mod_by(c, k) == 0]
    print(" ".join(ans) if ans else "none")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 04:10
 * update_at: 2026-10-05 04:10
 */
// main.cpp：逐位取模判断 30 位十进制大整数能被 2~9 中哪些数整除。
#include <iostream>
#include <string>

typedef long long ll;

std::string c; // c 的十进制表示，位数最多 30 位，只能按字符串读入

// 返回大整数 c 对 k 的余数：从高位到低位递推 r = (r * 10 + 当前位数字) % k
ll mod_big(ll k) {
    ll r = 0;
    ll len = c.size();
    for (ll i = 0; i < len; i++) {
        r = (r * 10 + (c[i] - '0')) % k;
    }
    return r;
}

int main() {
    std::cin >> c;
    bool found = false; // 是否已经找到至少一个因子，用来控制输出空格
    for (ll k = 2; k <= 9; k++) {
        if (mod_big(k) == 0) {
            if (found) {
                std::cout << ' ';
            }
            std::cout << k;
            found = true;
        }
    }
    if (!found) {
        std::cout << "none";
    }
    std::cout << std::endl;
    return 0;
}

目录

题目描述

思路

参考代码