Alien Invasion

#include <iostream>
#include <vector>
#include <map>
 
using namespace std;
typedef long long ll;
typedef __int128 lll;
 
ll n;
 
ll mrb[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
 
lll modpow(lll k, lll e, lll m) {
	if (e == 0) return 1;
	if (e == 1) return k;
	
	if (e%2 == 0) {
		lll h = modpow(k, e/2, m)%m;
		return (h*h)%m;
	}
	return (k*modpow(k, e-1, m))%m;
}
 
bool witness(ll a, ll x, ll u, ll t) {
	lll cx = modpow(a, u, x);
	for (int i = 1; i <= t; ++i) {
		lll nx = (cx*cx)%x;
		if (nx == 1 && cx != 1 && cx != (x-1)) {
			return true;
		}
		cx = nx;
	}
	return (cx != 1);
}
 
bool miller_rabin(ll x) {
	if (x == 2) return true;
	if (x < 2 || x%2 == 0) return false;
	
	ll u = x-1;
	ll t = 0;
	while (u%2 == 0) {
		u /= 2;
		t++;
	}
	
	for (int i = 0; i < 12; ++i) {
		if (mrb[i] >= x-1) break;
		if (witness(mrb[i], x, u, t)) return false;
	}
	return true;
}
 
ll f(lll x, lll m) {
	return (x*x+1)%m;
}
 
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
 
ll pollardrho(ll a, ll st) {
	if (n%2 == 0) return 2;
	ll x = st, y = st, d = 1;
	while (d == 1) {
		x = f(x, a);
		y = f(f(x, a), a);
		d = gcd(abs(x-y), a);
		if (d == a) return -1;
	}
	return d;
}
 
ll pdrive(ll x) {
	ll fa = -1;
	ll st = 2;
	while (fa == -1) {
		fa = pollardrho(x, st++);
	}
	return fa;
}
 
map<ll, ll> fact(ll x) {
	map<ll, ll> cres;
	while (!miller_rabin(x)) {
		ll cf = pdrive(x);
		cres[cf]++;
		x = (x/cf);
	}
	cres[x]++;
	return cres;
}
 
int main() {
	cin >> n;
	if (n == 1) {
		cout << "odd\n";
		return 0;
	}
	map<ll, ll> mp = fact(n);
	ll res = 1;
	for (auto a : mp) {
		res *= (a.second+1);
		res %= 2;
	}
	if (res%2 == 0) cout << "even\n";
	else cout << "odd\n";
	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: ACCEPTED

Test 20

Verdict: TIME LIMIT EXCEEDED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: WRONG ANSWER