FoxAndCake2 [TopCoderOpen 2017 Round2A Div1 Easy]

https://community.topcoder.com/stat?c=problem_statement&pm=14609&rd=16929

問題概要

チェリーがC個、いちごがS個ある。
これを以下のルールでグルーピングする。

• 全てのチェリーといちごが何処かのグループに入る
• 何グループに分けてもいい
• 各グループ1つはチェリーといちごがそれぞれある
• 各グループのチェリーといちごの数は互いに素になってはいけない

全て満たすように分割可能か

解説

• 7以上であれば2x+3yの形に必ず分割できる（誰かのツイートでみた）

なので、6以下で場合分けしている解答が多かったですが、愚直に分割する片方の数を[1,100]で回すと解ける。
[1,10]くらいで回せば十分だけど

int gcd(int a, int b) { return a ? gcd(b%a, a) : b; }
#define YES "Possible"
#define NO "Impossible"

struct FoxAndCake2 {
    string isPossible(int c, int s) {
        if (gcd(c, s) != 1) return YES;

        rep(a, 1, 101) rep(b, 1, 101) {
            int aa = c - a, bb = s - b;
            if (aa <= 0) continue;
            if (bb <= 0) continue;

            if (gcd(a, b) != 1 && gcd(aa, bb) != 1) return YES;
            if (gcd(a, bb) != 1 && gcd(aa, b) != 1) return YES;
        }

        return NO;
    }
};