SRM 375 DIV1 Easy - DivisibleByDigits

SRM 375 DIV1 Easy - DivisibleByDigits

13:44

問題


http://community.topcoder.com/stat?c=problem_statement&pm=8318&rd=10794

解き方


2~9すべての最大公約数は2520なので
答えは最大でもn+5桁程度であり、全探索が可能。

コード


class DivisibleByDigits {

public:

bool ispossible(long long x,vector<int> vx){
FORE(i,0,vx.size())if(x%vx[i]!=0)return false;
return true;
}

long long getContinuation(int n) {
set<int> s;
int x=n;
while(x>0){
s.insert(x%10);
x/=10;
}
vector<int> vx;
FORE(i,1,10)if(s.find(i)!=s.end())vx.push_back(i);

string str;
stringstream out;
out << n;
out >> str;

queue<string> q;
q.push(str);

while(!q.empty()){
string cur=q.front();
q.pop();

stringstream out2(cur);
long long p;
out2 >> p;
if(ispossible(p,vx))return p;

for(char ch='0';ch<='9';ch++){
q.push(cur+ch);
}
}

return -1;
}

};

Share this

Google Facebook Twitter More

Related Posts