2011 TCO Qualification Round 3 - AllButOneDivisor (○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11415&rd=14531
・ｎ個の数字が与えられる。
・このうち、n-1個の数字で割ることができ残りの数字で割ることのできない数のうち最小のものを求める。そのような数字がないときは-1を返す。
解き方
・数字の数は最大６個なので全探索できそう。
・n-1個の数字で割ることができる数、つまりn-1個の数字の最小公倍数がこれを満たす。
この数字が残りの数字で割ることができなければ解の候補となる。
逆に残りの数字で割ることができればどのようにとっても割ることができてしまうため満たさない。
→System Passed
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class AllButOneDivisor {
public:
int gcd(int x,int y){
return y ? gcd(y,x%y) : x;
}
int getMinimum(vector<int> divisors) {
int n=divisors.size();
int ret=1e+9;
FORE(i,0,n){
int p=1;
FORE(j,0,n)if(i!=j)p=p*divisors[j]/gcd(p,divisors[j]);
if(p%divisors[i])ret=min(ret,p);
}
return ret==1e+9 ? -1 : ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class AllButOneDivisor {
public:
int gcd(int x,int y){
return y ? gcd(y,x%y) : x;
}
int getMinimum(vector<int> divisors) {
int n=divisors.size();
int ret=1e+9;
FORE(i,0,n){
int p=1;
FORE(j,0,n)if(i!=j)p=p*divisors[j]/gcd(p,divisors[j]);
if(p%divisors[i])ret=min(ret,p);
}
return ret==1e+9 ? -1 : ret;
}
};
