大整数的因子

题意

给定最多 $30$ 位的非负整数，输出 $2$ 到 $9$ 中能整除它的所有数；没有则输出 none。

思路

对每个候选除数，从左到右维护已读前缀的余数。读入下一位 digit 后，新余数为 (remainder * 10 + digit) % divisor。最终余数为零便说明整除。

这种写法不依赖把整串数字转为整数，也适用于更长的十进制数。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11number = input().strip()
divisors = []

for divisor in range(2, 10):
    remainder = 0
    for digit in number:
        remainder = (remainder * 10 + int(digit)) % divisor
    if remainder == 0:
        divisors.append(str(divisor))

print(" ".join(divisors) if divisors else "none")

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#include <cstdio>
#include <cstring>
char str[50];
bool is_exists = false;

int main(){
    scanf("%s",str);
    int i,j,len = strlen(str);
    for (i=0;i<len;i++){
        str[i] -='0';
    }
    for (i=2;i<=9;i++){
        int pre = 0;
        for(j=0;j<len;j++){
            int num = pre*10+str[j];
            pre = num % i;
        }
        if( !pre){
            printf("%d ",i);
            is_exists = 1;
        }
    }
    if(!is_exists)
        printf("none");
    return 0;
}

复杂度

设数字长度为 $d$ ，候选除数固定为 $8$ 个，时间复杂度为 $O(d)$ ，额外空间复杂度为 $O(1)$ 。

总结

逐位取模是处理超长整数整除性的通用模板。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结