CSES - HIIT Open 2018 - Results
Submission details
Task:Alien Invasion
Sender:Oispa nutellaa
Submission time:2018-05-26 11:58:12
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.02 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.01 sdetails
#6ACCEPTED0.01 sdetails
#7ACCEPTED0.01 sdetails
#8ACCEPTED0.01 sdetails
#9ACCEPTED0.01 sdetails
#10ACCEPTED0.01 sdetails
#11ACCEPTED0.01 sdetails
#12ACCEPTED0.01 sdetails
#13ACCEPTED0.01 sdetails
#14ACCEPTED0.01 sdetails
#15ACCEPTED0.01 sdetails
#16ACCEPTED0.01 sdetails
#17ACCEPTED0.01 sdetails
#180.01 sdetails
#19ACCEPTED0.01 sdetails
#20--details
#21ACCEPTED0.01 sdetails
#220.01 sdetails

Code

#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 details

Test 1

Verdict: ACCEPTED

input
1

correct output
odd

user output
odd

Test 2

Verdict: ACCEPTED

input
2

correct output
even

user output
even

Test 3

Verdict: ACCEPTED

input
3

correct output
even

user output
even

Test 4

Verdict: ACCEPTED

input
4

correct output
odd

user output
odd

Test 5

Verdict: ACCEPTED

input
5

correct output
even

user output
even

Test 6

Verdict: ACCEPTED

input
6

correct output
even

user output
even

Test 7

Verdict: ACCEPTED

input
7

correct output
even

user output
even

Test 8

Verdict: ACCEPTED

input
8

correct output
even

user output
even

Test 9

Verdict: ACCEPTED

input
9

correct output
odd

user output
odd

Test 10

Verdict: ACCEPTED

input
10

correct output
even

user output
even

Test 11

Verdict: ACCEPTED

input
11

correct output
even

user output
even

Test 12

Verdict: ACCEPTED

input
12

correct output
even

user output
even

Test 13

Verdict: ACCEPTED

input
13

correct output
even

user output
even

Test 14

Verdict: ACCEPTED

input
14

correct output
even

user output
even

Test 15

Verdict: ACCEPTED

input
15

correct output
even

user output
even

Test 16

Verdict: ACCEPTED

input
16

correct output
odd

user output
odd

Test 17

Verdict: ACCEPTED

input
17

correct output
even

user output
even

Test 18

Verdict:

input
18

correct output
even

user output
odd

Test 19

Verdict: ACCEPTED

input
19

correct output
even

user output
even

Test 20

Verdict:

input
999999874000003969

correct output
odd

user output
(empty)

Test 21

Verdict: ACCEPTED

input
999999999999999989

correct output
even

user output
even

Test 22

Verdict:

input
1000000000000000000

correct output
odd

user output
even