Submission #5896070

---

Source Code Expand

#include <iostream>
#include <set>
#define llint long long

using namespace std;

llint n;
llint a[10005], b[10005];
set<llint> S;

int main(void)
{
	cin >> n;
	for(llint i = n; i >= 0; i--) cin >> b[i];
	
	llint k = 0;
	for(llint i = 0; i <= n; i++){
		if(b[i]){
			k = i;
			break;
		}
	}
	for(llint i = 0; i <= n-k; i++) a[i] = b[i+k];
	n -= k;
	
	llint m = abs(a[0]);
	for(llint i = 1; i*i <= m; i++){
		if(m%i) continue;
		S.insert(i), S.insert(m/i);
	}
	for(int i = 1; i <= n+k; i++) S.insert(i);
	
	for(auto p : S){
		bool flag = true;
		if(p == 1) flag = false;
		for(llint i = 2; i*i <= p; i++){
			if(p % i == 0){
				flag = false;
				break;
			}
		}
		if(!flag) continue;
		
		for(llint i = 0; i <= n; i++){
			b[i] = a[i];
			if(b[i] < 0) b[i] = p - (-b[i]) % p;
			b[i] %= p;
		}
		for(llint i = n; i >= p-1; i--){
			if(b[i] == 0) continue;
			if(k == 0 && i == p-1) continue;
			b[i-(p-1)] += b[i], b[i-(p-1)] %= p;
			b[i] = 0;
		}
		
		flag = true;
		for(llint i = 0; i <= n; i++){
			if(b[i]) flag = false;
		}
		if(flag) cout << p << endl;
	}
	return 0;
}

Submission Info

Judge Result