AtCoder ABC #420 : G - sqrt(n²+n+X)

Fの方が難しかった。
https://atcoder.jp/contests/abc420/tasks/abc420_g

問題

整数Xが与えられる。が整数となるような整数nを列挙せよ。

解法

整数aを用いてとなると仮定する。
式変形するととなる。
右辺が整数になればいいので、aをO(√X)程度総当たりして、分母が分子を割り切るか試せばよい

ll X;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X;
	vector<ll> R;
	for(ll a=-50000000;a<=50000000;a++) {
		ll v=a*a-X;
		if(v%(1-2*a)==0) {
			R.push_back(v/(1-2*a));
		}
	}
	
	
	sort(ALL(R));
	R.erase(unique(ALL(R)),R.end());
	cout<<R.size()<<endl;
	FORR(r,R) cout<<r<<" ";
	cout<<endl;
}

まとめ

色んな式変形の方式がありそう。