問題
http://community.topcoder.com/stat?c=problem_statement&pm=11817&rd=14730
解き方
A，B自身をXとYで表せられるような整数を求めれば良い。
どちらもXで割り切れるならばYが不要になるので−１となる。
コード
class KingXNewCurrency {
public: int howMany(int A, int B, int X) {
if(A%X==0 && B%X==0)return -1;
set<int> s1,s2;
for(int i=0;i<A;i+=X)for(int j=1;j<=A-i;j++){
if((A-i)%j==0)s1.insert(j);
}
for(int i=0;i<B;i+=X)for(int j=1;j<=B-i;j++){
if((B-i)%j==0)s2.insert(j);
}
if(A%X==0)return s2.size();
if(B%X==0)return s1.size();
int ret=0;
for(set<int>::iterator it=s1.begin();it!=s1.end();it++){
if(s2.find(*it)!=s2.end())ret++;
}
return ret;
}
};
public: int howMany(int A, int B, int X) {
if(A%X==0 && B%X==0)return -1;
set<int> s1,s2;
for(int i=0;i<A;i+=X)for(int j=1;j<=A-i;j++){
if((A-i)%j==0)s1.insert(j);
}
for(int i=0;i<B;i+=X)for(int j=1;j<=B-i;j++){
if((B-i)%j==0)s2.insert(j);
}
if(A%X==0)return s2.size();
if(B%X==0)return s1.size();
int ret=0;
for(set<int>::iterator it=s1.begin();it!=s1.end();it++){
if(s2.find(*it)!=s2.end())ret++;
}
return ret;
}
};