When the number of common divisors is odd, only when the greatest common divisor can be expressed by the square of some number. Isqrt is a function newly implemented in Python 3.8.
from math import gcd, isqrt
A, B = map(int, input().split())
X = gcd(A, B)
if isqrt(X) * isqrt(X) == X:
print('Odd')
else:
print('Even')
Since the test is weak, if the greatest common divisor is not divisible by a number less than 10 7 </ sup>, it is output as Odd, otherwise the greatest common divisor is factorized into the number of divisors. You can also AC by asking for. Why isn't there a case where the greatest common divisor is a prime number of 10 9 </ sup> or more, or is it not in the test case? ..
#include <bits/stdc++.h>
#define rep(i, a) for (int i = (int)0; i < (int)a; ++i)
using namespace std;
using ll = long long;
int main() {
ll A, B;
cin >> A >> B;
ll X = gcd(A, B);
if (X == 1) {
cout << "Odd" << endl;
return 0;
}
bool flag = false;
for (ll i = 2; i < 1e7; i++) {
if (X % i == 0) {
flag = true;
break;
}
}
if (!flag) {
cout << "Odd" << endl;
return 0;
}
ll result = 1;
ll t = 0;
while (X % 2 == 0) {
t++;
X /= 2;
}
result *= t + 1;
for (ll i = 3; i < (ll)(sqrt(X) + 1); i += 2) {
if (X % i != 0) continue;
ll t = 0;
while (X % i == 0) {
t++;
X /= i;
}
result *= t + 1;
}
if (X != 1) {
result *= 2;
}
if (result % 2 == 0) {
cout << "Even" << endl;
} else {
cout << "Odd" << endl;
}
return 0;
}
The sum of odd numbers is even, so you can win if you give only odd numbers.
N = int(input())
print(*range(1, N + 1, 2))
You can win even if you put out only the second half.
N = int(input())
print(*range(N // 2 + 1, N + 1))
Recommended Posts