AGC025D Choosing Points

Link
两个限制分开考虑都是二分图独立集，那么现在相当于给了一个四染色的图需要求一个不小于(frac{|V|}4)的独立集，由鸽巢原理可知取最大的一种颜色的点集一定满足条件。
直接做的话是(O(n^2c))的，(c)是(x^2+y^2=d)的非负整数解数。
考虑如何在不建图的情况下完成二分图染色，设(d=2^{2k}p(4 mid p))。
那么所有距离为(d)的点对都可以写成((2^ku,2^kv))的形式，其中(u^2+v^2=p^2)。
考虑(mod 2^k)的等价类，当(pequiv3pmod4)时显然不存在合法点对。
若(pequiv1pmod4)，那么(u,v)为一奇一偶，按(u+v)的奇偶性染色即可。
若(pequiv2pmod4)，那么(u,v)都是奇数，按(u)的奇偶性染色即可。

#include<cstdio>
int check(int x,int y,int d){int c=__builtin_ctz(d);return c&1? !(x>>(c/2)&1):!((x^y)>>(c/2)&1);}
int main()
{
    int n,d1,d2;scanf("%d%d%d",&n,&d1,&d2);
    for(int c=0,i=0;i<n+n;++i)
	for(int j=0;j<n+n;++j)
	    if(check(i,j,d1)&&check(i,j,d2))
	    {
		printf("%d %d
",i,j);
		if(++c==n*n) return 0;
	    }
}