首页 > 试题广场 >

大整数的因子

[编程题]大整数的因子

热度指数：10783 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

输入描述:

若干个非负整数c，c的位数<=30
每行一个c

输出描述:

每一个c的结果占一行
1) 若存在满足 c%k == 0 的k，输出所有这样的k，中间用空格隔开，最后一个k后面没有空格。
2) 若没有这样的k则输出"none"

注意整数溢出问题
不要对-1进行计算

示例1

输入

输出

2 3 5 6
2 3 4 6 8 9
none

算法知识视频讲解

Java

菜鸟葫芦娃

直接用除法，思路就是上一位取余数*10加上当前位除以k，

一直到所有位判断完毕，这个其实就是手算除法的模拟过程

import java.util.Scanner;

*直接用除法，思路就是上一位取余数*10加上当前位除以k，

*一直到所有位判断完毕，这个其实就是手算除法的模拟过程

* */

public class BigNumer {

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner in = new Scanner(System.in);

while (in.hasNext()) {

String num = in.nextLine();

if (num.equals("-1")) {

break;

}

process(num);

}

in.close();

}

static void process(String num) {

StringBuffer buffer = new StringBuffer();

for (int k = 2; k < 10; k++) {

if (isContaineFactor(num, k)) {

buffer.append(k + " ");

}

if (buffer.length() > 0) {

buffer.delete(buffer.length() - 1, buffer.length());

}

else {

buffer.append("none");

}

System.out.println(buffer.toString());

}

static boolean isContaineFactor(String num, int k) {

int num1 = 0;

int num2 = 0;

int len = num.length();

for (int i = 0; i < len; i++) {

num1 = (num.charAt(i) - '0') + num2 * 10;

num2 = num1 % k;

}

return num2 == 0 ? true : false;

}

发表于 2016-07-21 12:05:46 回复(0)

C++

之一不之

大数取模

#include<bits/stdc++.h>
using namespace std;

bool Modzheng(string c,int k){
    int remander=0;
    for(int i=0;i<c.size();i++){
        int current=remander*10+c[i]-'0';
        remander=current%k;
        c[i]=current/k;
    }
    if(remander==0){
        return true;
    }else{
        return false;
    }
}

int main(){
    string c;
    while(cin>>c){
        if(c=="-1")break;
        int ans[10];
        int num=0;
        for(int k=2;k<=9;k++){
            if(Modzheng(c,k)){
                ans[num]=k;
                num++;
            }
        }
        if(num==0){
            cout<<"none"<<endl;
        }else{
            for(int i=0;i<num;i++){
                if(i==0){
                    cout<<ans[i];
                }else{
                    cout<<" "<<ans[i];
                }
            }
            cout<<endl;
        }
    }
    return 0;
}

发表于 2021-09-02 17:11:09 回复(0)

C/C++

牛客530521353号

#include <stdio.h>
#include <string.h>

//用字符串从高位到低位求余数：

int div(char *x, int y, int len){
int r = 0;
for(int j = 0; j < len; j++){
r = r * 10 + x[j] - '0';
r %= y;
}
return r;
}

int main(){
char c[30];
while(scanf("%s", c) != EOF){
if(c[0] == '-'){
break;
}
int flag = 0; //用作标记有无可以整除的k，及求得的第一个数，不输出空格；
int len = strlen(c);
for(int i = 2; i < 10; i++){
int r = div(c, i, len);
if(r == 0){
if(flag == 0){
printf("%d", i);
flag = 1;
}else{
printf(" %d", i); //如果不是第一个数，就在前面输出一个空格；
}
}
}
if(flag){
printf("\n");
}else{
printf("none\n");
}
}
return 0;
}

发表于 2021-03-23 16:24:07 回复(0)

用户抉择

#include <stdio.h>
#include <string.h>
int main()
{
    char a[30];
    int i,k,b[30],c,q;
    while(scanf("%s",&a)!=EOF)
    {
        if(!strcmp(a,"-1")) break;
        for(k=2,q=0;k<10;k++)
        {
            for(i=0,c=0;i<strlen(a);i++)
            {
                b[i]=(a[i]-'0')+c*10;
                c=b[i]%k;
                b[i]/=k;
            }
            if(c==0)
            {
                if(q==0)
                    printf("%d",k);
                else
                    printf(" %d",k);
                q++;
            }
        }
        if(q==0) printf("none\n");
        else printf("\n");
    }
    return 0;
}

发表于 2021-03-22 10:17:02 回复(0)

牛客530368524号

似乎最后并没有输入“-1”退出而是必须判断EOF？……反正去掉了判断!=EOF之后程序就超时，即使是判断第一个字符是否为‘-’也不行，必须判断EOF程序才能正常结束

#include <stdio.h>
#include <string.h>

#define N 31

char c[N];

int main(){
    while(scanf("%s", &c) != EOF){
        if(strcmp(c, "-1") == 0){
            break;
        }
        int count = 0;
        for (int k = 2; k <= 9; k++){
            int flag = 0;
            for (int i = 0; i < strlen(c); i++){
                flag = (flag * 10 + c[i] - '0') % k;
            }
            if(flag == 0){
                if(count == 0){
                    printf("%d", k);
                } else {
                    printf(" %d", k);
                }
                count++;
            }
        }
        if(count == 0){
            printf("none");
        }
        puts("");
    }
    return 0;
}

发表于 2021-03-13 21:21:16 回复(0)

fusnzusi

#include<stdio.h>
(737)#include<string.h>
#define N 100
int main()
{	
	char a[N];
	int flag;								//无符合输出none 
	while(scanf("%s",a)!=EOF)
	{
		flag=0; 
		if(a[0]=='-') break;
		int len=strlen(a);
		int num[len];
		for(int i=0;i<len;i++)
		num[i]=a[i]-'0';
		
		for(int i=2;i<10;i++)            //不断取模，最后为0则是因子
		{
			int remain=0;
			int temp=0;
			for(int j=0;j<len;j++)
			{	
				temp=10*remain+num[j];
				remain=temp%i;
			}
			if(remain==0) 
			{
				printf("%d ",i);
				flag=1;
			}
		}
		if(flag==0) printf("none");
		printf("\n");
	}	
	return 0;
}

发表于 2020-03-30 22:52:34 回复(0)

C/C++

算法小屁孩

#include<bits/stdc++.h>
char a[31];
int main(){
    while(scanf("%s ",a)!=EOF){
        int mark=0;
        for(int i=2;i<=9;i++){
            int s=0;
            for(int j=0;j<strlen(a);j++)
                s=(s*10+a[j]-'0')%i;
            if(s==0){
                printf("%d ",i);
                mark=1;
            }
        }
        if(mark==0) printf("none\n");
        else printf("\n");
    }
}

发表于 2019-03-18 13:04:49 回复(0)

✭

#include<iostream>
#include<string>
using namespace std;
//大整数求余数，余数为0则可以被整除
bool judge(string s,int a){
    int temp=0;
    for(int i=0;i<s.length();i++){
        temp=(temp*10+(s[i]-'0'))%a;
    }
    if(temp==0)
        return true;
    else
        return false;
}
int main(){
    string s;
    int sum[10];
    while(cin>>s){
        int flag=0;
        for(int i=2;i<10;i++){
            if(judge(s,i)){
                sum[flag++]=i;
            }
        }
        if(flag==0)
            cout<<"none"<<endl;
        else{
            for(int k=0;k<flag;k++){
                if(k==flag-1)
                    cout<<sum[k]<<endl;
                else
                    cout<<sum[k]<<' ';
            }
        }
    }
    return 0;
}

发表于 2019-03-08 22:14:34 回复(0)

Artintel

#include<cstdio>

#include<string.h>

int is(char a[],int k)

    int num[30];

    int i,len=strlen(a);

    for(i=0;i<len;++i)

        num[i]=a[i]-'0';

    if(num[0]<k)

        num[1]=num[0]%k*10+num[1];

        num[0]=k;

    for(i=1;i<len;++i)

        num[i]=num[i-1]%k*10+num[i];

    if(num[i-1]%k==0)

        return k;

    else return -1;

int main()

    char a[30];

    while(scanf("%s",a)!=EOF)

        int index[10]={0};

        int k,sum=0,i;

        for(k=2;k<=9;++k)

            if(is(a,k)==k)

                index[k]=1;

                sum++;

        if(sum==0)

            printf("none\n");

        else

            i=2;

            while(sum!=0)

                if(index[i]==1)

                    printf("%d",i);

                    if(sum>1)

                        printf(" ");

                    --sum;

                ++i;

            printf("\n");

    return 0;

发表于 2019-03-08 16:35:41 回复(0)

小陈也只是想要一个实习罢了

感觉自己做的非常麻烦，得要参考一下别人的hhh

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int main() {
    string str;
    getline(cin, str);
    char ch[30];
    strcpy(ch, str.c_str());
    int num = str.length();
    int out[8];
    int outCount = 0;
    if (ch[num-1] == '0' || ch[num-1] == '2' || ch[num-1] == '4' || ch[num-1] == '6' || ch[num-1] == '8') {
        out[outCount++] = 2;
        int temp = 0;
        for (int i = 0; i<num; i++)
            temp += ch[i] - '0';
        if (temp % 3 == 0)
            out[outCount++] = 6;
        temp = 0;
        temp = (ch[num-2] - '0') * 10 + ch[num-1] - '0';
        if (temp % 4 == 0)
            out[outCount++] = 4;
        temp = (ch[num-3] - '0') * 100+(ch[num-2] - '0') * 10 + ch[num-1] - '0';
        if (temp % 8 == 0)
            out[outCount++] = 8;
    }
    int total = 0;
    for (int i = 0; i<num; i++) {
        total += ch[i] - '0';
    }
    if (total % 3 == 0)
        out[outCount++] = 3;
    if (total % 9 == 0)
        out[outCount++] = 9;
    if (ch[num-1] == '0' || ch[num-1] == '5')
        out[outCount++] = 5;
    total = 0;
    if (num <= 3) {
        if (num == 1) {
            if (ch[0] == '7')
                out[outCount++] = 7;
        }
        if (num == 2) {
            if (((ch[0] - '0')*10 + (ch[1] - '0')) % 7 == 0)
                out[outCount++] = 7;
        }
        if (num == 3) {
            if (((ch[0] - '0')*100 + (ch[1] - '0') * 10 + (ch[2] - '0')) % 7 == 0)
                out[outCount++] = 7;
        }
    }
    else {
        for (int i = num - 4; i>=0; i--) {
            if (i == num - 4)
                total = (ch[i] - '0') * 100 + (ch[i + 1] - '0') * 10 + (ch[i + 2] - '0') - (ch[i + 3] - '0') * 2;
            else {
                total += (ch[i] - '0') * 1000;
                int temp1 = total % 10;
                total /= 10;
                total = total - temp1 * 2;
            }
        }
        if (total % 7 == 0)
            out[outCount++] = 7;
    }
    sort(out, out + outCount);
    if (outCount>0) {
        for (int i = 0; i<outCount; i++) {
            if (i == outCount - 1)
                cout << out[i];
            else
                cout << out[i] << " ";
        }
       cout << endl;
    }
    else
        cout << "none" << endl;
}

发表于 2019-02-07 16:11:51 回复(1)

Daniel_Ni

#include <stdio.h>
#include <string.h>

#define  maxDigits    (10)
struct bigInteger {
    int digit[10];
    int size;

    void init() {
        for (int i = 0; i < maxDigits; ++i)
            digit[i] = 0;
        size = 0;
    }

    void set(char str[]) {
        init();
        int L = strlen(str);

        /* j control each four char to save as one digit,
         * t refer to one digit temporary, while c as weight,
         */
        for (int i = L-1, j=0, t=0, c=1; i >= 0; i--) {
            t += (str[i]-'0')*c;
            j++;
            c *= 10;
            /* i == 0 for ending, if rest of str is less than four */
            if (j == 4 || i == 0) {
                digit[size++] = t;
                j = 0;
                t = 0;
                c = 1;
            }
        }
    }

    int operator % (int x) const {
        int remainder = 0;
        for (int i = size-1; i >= 0; --i) {
            remainder = (remainder*10000+digit[i]) % x;
        }

        return remainder;
    }
};


int main()
{
    bigInteger a;
    char str[40];    

    while (scanf("%s", str) != EOF) {
        if (strlen(str) == 2 && str[0] == '-' && str[1] =='1')
            continue;

        a.set(str);

        int found = 0;
        for (int i = 2; i <= 9; ++i) {
            if (a % i == 0) {
                printf("%s%d", found ? " " : "", i);
                found = 1;
            }
        }
        printf("%s", found ? "\n" : "none\n");
    }

    return 0;
}

发表于 2019-01-28 16:03:55 回复(0)

Python

TimeMac

try:
    while True:
        num = int(input())
        result = []
        for i in range(2,10):
            if num % i == 0:
                result.append(i)
        if result:
            print(" ".join(map(str,result)))
        else:
            print('none')
except Exception:
    pass

编辑于 2018-10-08 22:24:16 回复(0)

C/C++

_stormpang

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 31;

int bite[10];       // bite[2]-bite[9] 作为标志变量用于最后输出
int br[maxn];       // 存储输入的整数

// 将字符串对应到 br 中
void change(string str)
{
    memset(br, 0, sizeof(br));

    for(int i = 0; i < str.length(); ++i)
    {
        br[++br[0]] = str[i]-'0';
    }

}

// 计算 2 - 9
void solve()
{
    memset(bite, 0, sizeof(bite));

    int y = 0;
    int i = 1;
    for(int j = 2; j <= 9; ++j)
    {
        y = 0;
        i = 1;
        while(i <= br[0])
        {
            y = y * 10 + br[i++];
            y %= j;
        }
        bite[j] += y;
    }
}

// 输出
void output()
{
    int flag = 0;
    for(int j = 2; j <= 9; ++j)
    {
        if(bite[j] == 0)
        {
            if(flag == 1)
            {
                cout << " ";
            }
            flag = 1;
            cout << j;
        }
    }
    if(flag == 0)
    {
        cout << "none";
    }
}

int main()
{
    
    string str;
    while(cin >> str)
    {
        if(str == "-1")
        {
            break;
        }

        change(str);
        solve();
        output();
        cout << endl;

    }

    return 0;
}

发表于 2016-08-07 15:00:48 回复(0)

啥

用python的注意要用raw_input().strip(),而不要直接用input()

while True:
    try:
        num = int(raw_input().strip())
        if num == -1:
            break
        rlt = []
        for k in range(2, 10):
            if num%k == 0:
                rlt.append(k)
        rlt = map(str, rlt)
        if rlt:
            print ' '.join(rlt)
        else:
            print 'none'
    except:
        break

发表于 2016-03-25 22:29:52 回复(0)

Java

碧波晚晴

import java.math.BigInteger;
import java.util.*;

public class Main {
    public  static  void  main(String[] args) {
       Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            String c = input.nextLine();
            boolean flag = true;
            if ("-1".equals(c)) {
                break;
            } else {
                BigInteger big = new BigInteger(c);
                for (int i = 2; i <= 9; i++) {
                    if (big.mod(BigInteger.valueOf(i)).intValue() == 0) {
                        if (!flag) {
                            System.out.print(" ");
                        }
                        System.out.printf("%d", i);
                        flag = false;
                    }
                }
            }
            if (flag) {
                System.out.println("none");
            } else {
                System.out.println();
            }
        }
    }
}

发表于 2020-02-28 09:39:59 回复(0)

263保洁小妹

大数取模，和大数乘法有相似之处，高位取模，然后乘10加下一位，继续取模

#include <stdio.h>
#include <string.h>
#define N 31

int main()
{
    char str[N];
    int c[N];
    int mod;
    int count;
    while(gets(str))
    {
        if(str[0]=='-') break;
        int len=strlen(str);
        for(int i=0; i<len; i++)//高位在前
        {
            c[i]=str[i]-'0';
        }
        count=0;
        for(int k=2; k<=9; k++)
        {
            mod=0;
            for(int i=0; i<len; i++)
            {
                mod=(mod*10+c[i])%k;
            }
            if(mod==0)
            {
                if(count>0) printf(" ");
                printf("%d", k);
                count++;
            }
        }
        if(count==0) printf("none");
        printf("\n");
    }
    return 0;
}

发表于 2018-02-22 08:40:32 回复(3)

元气の悟空

#include<string>
#include<iostream>
using namespace std;
int mod(string a,int b){  
    int d=0;  
    for(int i=0;i<a.size();i++) d=(d*10+(a[i]-'0'))%b;
    return d;  
}
int main(){
    string x;
    while(cin>>x&&x!="-1"){
        int k,flag=0;
        for(k=2;k<=9;k++)
            if(!mod(x,k)){
				if(flag) printf(" ");
                else flag=1;
                printf("%d",k);
            }
        if(!flag) printf("none");
        printf("\n");
    }
}

发表于 2017-08-05 11:25:15 回复(3)

Python

华科平凡

while True:
    try:
        a,res=int(input()),[]
        if a==-1:break
        for i in range(2,10):
            if a%i==0:
                res.append(str(i))

        print(" ".join(res) if res else "none")
    except:
        break

发表于 2017-10-07 21:38:50 回复(2)

C/C++

YhX.

#include<stdio.h>
(737)#include<string.h>
int main()
{
    char a[30];
    int b[30],i,j,n,key=0,yushu;
    scanf("%s",a);
    n=strlen(a);
    for(i=0;i<n;i++)//字符数组转换成整数数组
        b[i]=a[i]-'0';
    for(i=2;i<10;i++)
    {
        yushu=0;
        for(j=0;j<n;j++)//直接从高位一直取余数
            yushu=(yushu*10+b[j])%i;
        if(yushu==0)
        { printf("%d ",i); key=1;}//表示存在
    }
    if(key==0) printf("none");
}

发表于 2020-03-31 21:55:29 回复(2)

C/C++

forestjylee

#include<cstring>
(803)#include<iostream>
using namespace std;


int main() {
    string s;
    int carry;
    while(cin>>s) {
        string res="";
        for(int k=2; k<=9; ++k) {
            string tmp(s);
            carry=0;
            for(int i=0; i<tmp.size(); ++i) 
                carry = (carry*10+tmp[i]-'0') % k;
            if(carry == 0) res+=char(k+'0');
        }
        if(res.empty()) cout<<"none"<<endl;
        else {
            for(int i=0; i<res.size()-1; ++i) 
                cout<<res[i]-'0'<<' ';
            cout<<res[res.size()-1]<<endl;
        }
    }
}

发表于 2020-05-01 11:44:56 回复(0)