プロジェクトオイラー問504 - sinapusu2002 @ ウィキ

教科書の公式を変形すると内部の点個数をＰとすると
２Ｐ＝(b+d)(a+c)+2-(gcd(a,b)+gcd(b,c)+gcd(c,d)+gcd(d,a))だけれど。
ＡＢＣを全部求めてＡＣＤをそれに対する追補として求めれば計算量落ちるな。
と思ったが。
m=100だったので機械的に解いた。
何だろうこの問題。
プロジェクトオイラーの最近の問題の中でも驚異的に優しい。
コード記述時間入れて15分で解けた。

#include <iostream>
#include <set>
using namespace std;

const int LIMIT=100;
int gcdMemo[LIMIT+1][LIMIT+1];

int gcd ( int a, int b )
{
  int c;
  while ( a != 0 ) {
     c = a; a = b%a;  b = c;
  }
  return b;
}


int main() {
	// your code goes here
	std::set<int> hit;
	for(int p=1;p<=300;p++){
		hit.insert(p*p*2);
	}
	for(int a=1;a<=LIMIT;a++){
		for(int b=1;b<=LIMIT;b++){
			gcdMemo[a][b]=gcd(a,b);
		}
	}
	
 	long long int ans=0;
	for(int a=1;a<=LIMIT;a++){
		for(int b=1;b<=LIMIT;b++){
			for(int c=1;c<=LIMIT;c++){
				for(int d=1;d<=LIMIT;d++){
					int s=(a+c)*(b+d)+2-gcdMemo[a][b]-gcdMemo[b][c]-gcdMemo[c][d]-gcdMemo[d][a];
					if(hit.find(s)!=hit.end()){
						ans++;
					}
				}
			}
		}
	}
	std::cout<<ans;
	return 0;
}