算法1
(暴力枚举) $O(n^2)$
高精度除法
在pd()函数中,模拟除法法则,求出a代表的数除t的余数,余数为0,表示能整除,返回true,否则,返回false
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int n;string s;vector<int> a;
bool pd(int t){
int yu = 0;
for(int i=0;i<n;i++){
yu = yu*10+a[i];
yu %= t;
}
return yu==0 ? true : false;
}
int main(){
while(cin>>s){
if(s=="-1") break;
n = s.size();
a.clear();
for(int i=0;i<n;i++) a.push_back(s[i]-'0');
bool tag = false;
for(int i=2;i<=9;i++)
if(pd(i)){
cout<<i<<" ";
tag = true;
}
if(!tag) cout<<"none";
cout<<endl;
}
return 0;
}