1605 - 大整数的因子

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

Input

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

每行一个c，当c=-1时中止
（不要对-1进行计算！）

Output

每一个c的结果占一行

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

Examples

Input

Output

3 7 9
2
none

Solution C

int len;
int cmp(int a[],int k)
{int i;
  
for(i=0;i<len-1;i++)
  a[i+1]+=(a[i]%k)*10;
if(a[i]%k==0) return 1;
else return 0;
}

int main(int argc, char* argv[])
{char num[31];
int i,b[11],j,k,tem[31];

while(gets(num))
{
if(num[0]=='-'&&num[1]=='1')break;
  len=strlen(num);
j=0;
for(k=2;k<10;k++)
{ 
	for(i=0;i<len;i++)
     tem[i]=num[i]-'0';  
 if(cmp(tem,k)) b[j++]=k;
}

if(j==0)printf("none\n");
 else for(i=0;i<j;i++)
  printf(j-i==1?"%d\n":"%d ",b[i]);

}
	return 0;
}

Solution C++

#include <iostream>
#include <string>
using namespace std;

bool isDiv(string s,int k){
    int v = 0, r = 0;
    for(int i=0;i<s.length();i++){
        v = (s[i]-'0') + r * 10;
        r = v%k;
    }
    if(r==0){
        return true;
    }
    else{
        return false;
    }
}

int main(){
    string s;
    while(cin>>s){
        if(s=="-1"){
            return 0;
        }
        bool flag = true;
        for(int i=2;i<10;i++){
            if(isDiv(s,i)){
                if(flag){
                    cout<<i;
                }
                else{
                    cout<<" "<<i;
                }
                flag = false;
            }
        }
        if(flag){
            cout<<"none";
        }
        cout<<endl;
    }
    return 0;
}

Time Limit	1 second
Memory Limit	32 MB

Discuss Stats

上一题下一题