SRM537 Div1 Easy(275), Div2 Medium(550) KingXNewCurrency

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;
}};