SRM537 Div1 Easy(275), Div2 Medium(550) KingXNewCurrency
XとYが題意を満たすことと、AもBもXp+Yqの形で表せることは、同値である。なぜなら、XとYが題意を満たせば当然AとBはXとYで表せるし、AとBがXとYで表せるならばAp+BqのAとBをそのXとYで置き換えれば良いから。XのみでAもBも表せるならば、Yは何でも良いので、-1を返す。max(A,B)より大きなYに意味はないので、Y≦max(A,B)まで調べれば良い。
#include <algorithm> using namespace std; class KingXNewCurrency{public: int howMany( int A, int B, int X ) { if ( A%X==0 && B%X==0 ) return -1; int ans = 0; for ( int Y=1; Y<=max(A,B); Y++ ) { bool a = false; for ( int p=0; X*p<=A; p++ ) if ( (A-X*p)%Y==0 ) a = true; bool b = false; for ( int p=0; X*p<=B; p++ ) if ( (B-X*p)%Y==0 ) b = true; if ( a && b ) ans++; } return ans; }};