yukicoder : No.1498 Factorization from -1 to 1

数学問。
https://yukicoder.me/problems/no/1498

問題

100000以下の正整数Xが与えられる。(X^2+1)を素因数分解せよ。

解法

X^2 + 1 ≡ 0 (mod P)なら、Y ≡ -XまたはY ≡ X (mod P)であるYに対し、Y^2 + 1 ≡ 0 (mod P) である。
そこで、f(X) = X^2+1とし、f(1)～f(X)をエラトステネスの篩の要領で処理する。

f(X)をXの小さい順に処理する。
もしf(X)が1より大きいなら、f(n*f(X)+X)およびf(n*f(X)-X)をf(X)で割れるだけ割ってみよう。

ll X[1010101];
vector<ll> V[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=100001;i++) X[i]=1LL*i*i+1;
	for(i=1;i<=100001;i++) if(X[i]>1) {
		ll p=X[i];
		
		for(ll x=i;x<=100001;x+=p) {
			while(X[x]%p==0) X[x]/=p, V[x].push_back(p);
		}
		for(ll x=p-i;x<=100001;x+=p) {
			while(X[x]%p==0) X[x]/=p, V[x].push_back(p);
		}
	}
	
	int Q;
	cin>>Q;
	while(Q--) {
		cin>>x;
		sort(ALL(V[x]));
		FOR(i,V[x].size()) {
			cout<<V[x][i];
			if(i<V[x].size()-1) cout<<" ";
		}
		cout<<endl;
	}
	
	
}

まとめ

これは思いつかないなぁ…。