c++习题29-大整数的因子

本文主要是介绍c++习题29-大整数的因子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一，题目

二，思路

三，代码

一，题目

描述

已知正整数k满足2≤k≤9，现给出长度最大为30位的十进制非负整数c，求所有能整除c的k。

输入描述

一个非负整数c，c的位数≤30。

输出描述

若存在满足 c%k == 0 的k，从小到大输出所有这样的k，相邻两个数之间用单个空格隔开；若没有这样的k，则输出"none"。

用例输入 1

用例输出 1

2 3 5 6

二，思路

根据题目输入要求：输入一个非负整数c，c的位数≤30，可以看到输入的是一个很大的整数，超出了标准数据类型的范围，需要使用其它变量存储，例如：vector容器和string类，这里推荐使用string类，因为需要输入一行整数，string类可以直接使用一条语句cin输入就行。因此需要定义一个string类型的字符串变量s：string s; 之后使用输入流对象cin 从键盘输入获取数据：cin>>s; 这里我输入 12345
根据题目输出要求：如果输入的整数能够整除k （ $k\in [2,9]$ ）中的数（可以是多个），就需要从小到大输出所有这样的k，若没有这样的k，则输出"none"。因此，我想到的就是给一个布尔类型的变量 no 来存储该整数没有这样的k ，既 bool no=true; （小旗子立着）默认这个整数确实在 $k\in [2,9]$ 这个区间内没有因子。中间的程序用来处理这个整数（判断该整数是否在指定区间内有因子，有因子，则将变量 no 赋值为 false ：该整数有因子）。因此，第二步可以在程序的末尾写上代码 if(no) cout<<"none"；既，经过了中间代码的判断，no 依旧是true ，则表示该整数在指定区间内没有因子，输出字符串"none"。
现在开始编写处理整数的代码：
1）可以放置一个外层循环，依次取到 k 所有取值   $k\in [2,9]$ ，既 for(int k=2;k<=9;k++)
2）
①  之后从字符串的第一位开始依次取出里面的字符for(char d:s)，可以遍历出存储大整数的字符串中的所有字符：‘1’，‘2’，‘3’，‘4’，‘5’。
②  将每一次取出的字符减去字符零 '0'得到该字符所显示数字的整数形式，例如‘1’-‘0’=1, ‘2’-‘0’=2 ，之后再随着外层循环中 k 的变化依次模 k的所有取值，将结果使用变量 r 存储（虽然需要存储的数值没有超出标准数据类型的范围，但是数值较大，建议用超长整数类型long long 存储）,并且，该变量 r 需要定义在外层循环和从字符串中取字符的中间（例如，第一次判断该整数是否能够整除2 ，如果不能，就将结果 r 置零，接着判断能否整除3....一直到 k=9 ），并且，后一个字符的计算结果与前一个字符的计算结果有关：
·  输入12345。第一个一个字符 '1' 不能被 2 整除（这里以k=2为例，也可以代入3.....9），r=(‘1’-‘0’)% 2 =1%10=1，1 不能整除 2，此时r=1，接着判断第二个字符'2'，r=('2'-'0')% 2=0
但是，这里有问题，如果按照 r=( c - '0' ) % k ;的想法来判断的话，只能判断末尾的数字是否能够被 $k\in [2,9]$ 整除，上面的12 能够被2整除，也能够被3整除，但12 的结尾是2，2不能整除3 ，3这个因子被排除掉了，例如像 12345，按照这种计算，最后只有一个因子 5 ，但是正确答案是 3 和 5这两个因子，因为对于3来说，如果该整数的每一位相加得到的结果能够整除3，那么这个整数即使不是3的倍数结尾的，它也是 3 的倍数（3是该整数的因子），12345每一位相加：1+2+3+4+5=3+7+5=15, 15%3=0；
· 因此，需要对   r=( c - '0' ) % k ; 进行修改，如果 12 的第一个字符 ‘1’ 不能整除3 ，r=1，到第二个字符的时候，就将之前的 r=1 保留，将它乘 10，加上第二个字符的 ‘2’，r=(r*10+('c'-'0'))%3=(1*10+'2'-'0')%3=(10+2)%3=12%3=0，这种判断才对，如果有三位数，则继续乘10（字符有多少个，就会执行多少次）
3）通过第二步的计算（内层的for循环结束），可以知道该大整数能否被对应的 k
（ $k\in [2,9]$ )，既遍历整个字符串之后，如果r ==0，那么就表示该大整数能够被对应的 k 整除，直接使用cout输出对应的 k ，并且将默认该整数没有因子的变量 no 赋值为 false （小旗子倒下），表示该大整数有因子，程序不需要再输出“none”。

三，代码

#include <bits/stdc++.h>
using namespace std;
int main() {string s;cin>>s;bool no=true;for (int k=2;k<=9;k++) {long long r=0;for(char c:s){r=(r*10+(c-'0'))%k;}if(r==0){cout<<k<<" ";no=false;}}if (no)  cout<<"none";return 0;
}

有问题请在评论区留言或者是私信我，回复时间不超过一天。

这篇关于c++习题29-大整数的因子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！