yukicoder : No.2847 Birthday Attack

サンプルにしてやられた。
https://yukicoder.me/problems/no/2847

問題

2整数X,Yが与えられる。
2次元座標で、(1,1)-(X,Y)の各格子点を中心として、半径1～10^9の円がそれぞれ書かれている。
ここに、陰陽玉を拡大縮小回転して作れる記号はいくつ存在するか。

解法

陰陽玉は、3つの点が一直線で等間隔に、かつそれらの距離が整数で並んでいると、その3点を中心とする円から2つ作ることができる。
言い換えると、距離が偶数にある2点ごとに(中点も格子点になるので)2つ作ることができる。

2点が縦及び横にならんているケースは容易に列挙できる。
問題は斜めのケースだが、これは原始ピタゴラス数を列挙することで対応できる。

ll X,Y;
ll mo;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>Y>>mo;
	ll ret=0;
	for(i=1;i<=4000000;i++) {
		if(X>=i*2) (ret+=(X-i*2)*(Y))%=mo;
		if(Y>=i*2) (ret+=(Y-i*2)*(X))%=mo;
	}
	for(int m=1;m*m<=8000000;m++) {
		for(int n=1;n<m;n++) {
			if(m%2!=n%2&&__gcd(m,n)==1) {
				ll a=m*m-n*n;
				ll b=2*m*n;
				for(i=1;2*a*i<=X&&2*b*i<=Y;i++) (ret+=2LL*(X-2*a*i)*(Y-2*b*i))%=mo;
				for(i=1;2*a*i<=Y&&2*b*i<=X;i++) (ret+=2LL*(Y-2*a*i)*(X-2*b*i))%=mo;
			}
		}
	}
	ret=ret*2%mo;
	cout<<ret%mo<<endl;
}

まとめ

最初まんまと斜めを見落としてしまった。