TopCoderOpen 2017 Round2A Easy FoxAndCake2

連続レート増は12回止まりでした。
https://community.topcoder.com/stat?c=problem_statement&pm=14609

問題

2つの正整数A,Bが与えられる。
いくつかの正整数の組のうち、互いに素でないものを組み合わせ、総和がA,Bとすることはできるか。

解法

A≦Bとする。
小さい数字で総当たりで試すと、以下の知見が得られる。

• A=1の時、解なし
  • 組選ぶ数字は2以上でしかないので明らか
• A=2またはA=4の時Bが奇数なら解なし
  • 単一の組で条件を満たすことはできないし、2つの組を選ぼうにも(1,*)+(1,*)、(1,*)+(3,*)、(2,*)+(2,*)どの選びかたも条件に反する。
• A=3の時Bが3の倍数でない解なし
  • 単一の組で条件を満たすことはできないし、2つの組を選ぼうにも(1,*)+(2,*)と片方は1を含んでしまい不可
• A=5の時Bが6の時解なし。
  • Bが7以上の奇数なら(3,3)+(A-3,B-3)で後者はともに偶数、Bが8以上の偶数なら(3,6)+(2,B-6)で後者はともに偶数となり、2つの整数の組で表現できる。
• A=6の時、Bが2または3の倍数でない場合解なし
• Aが7以上の場合、常に解あり
  • A=5の時同様、Bの偶奇に合わせて(3,3)か(3,6)どちらかを選べばよい。

class FoxAndCake2 {
	public:
	string isPossible(int a, int b) {
		if(a>b) swap(a,b);
		string A="Possible",B="Impossible";
		if(a==1) {
			return B;
		}
		else if(a==2 || a==4) {
			if(b%2) return B;
		}
		else if(a==3) {
			if(b%3) return B;
		}
		else if(a==5) {
			if(b==6) return B;
		}
		else if(a==6) {
			if(b%2 && b%3) return B;
		}
		
		return A;
		
	}
}

まとめ

自分は総当たりしたけど、ほかの人はどうやってこの知見を得たのだろう。