yukicoder : No.1125 Without Parallelogram

これはEditorialを見てしまったので…。
https://yukicoder.me/problems/no/1125

問題

正整数Nが与えられる。
(0,0)-(N+40,N+40)の矩形の範囲内でN個の異なる格子点を選択し、どの4点も平行四辺形を成さないようにせよ。

解法

Editorialまんまなんだけど、Nより大きな最小の素数Mを選び、1≦x≦Nの範囲で(x,x*(x-1)/2 mod M)を取ればよい。
これが正しいことを確認するには、2点を結ぶ線分が同じ向き・長さとなるケースがどれも1つしかないことを示せばよい。
f(x)=x*(x-1)/2 mod Mとして、X座標の等しい(x,f(x))-(x+i,f(x+i))と(y,f(y))-(y+i,f(y+i))の2つの頂点対を考えたとき、f(x+i)-f(x)=f(y+i)-f(y)となるのはx=yの時だけということから確認できる。

int N;

bool isprime(ll v) {
	for(ll i=2;i*i<=v;i++) if(v%i==0) return false;
	return (v!=1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int M;
	for(M=N+1;;M++) if(isprime(M)) break;
	
	for(i=1;i<=N;i++) {
		cout<<i<<" "<<i*(i+1)/2%M<<endl;
	}
	
}

まとめ

これ系の問題本番に解くのしんどそう。