Codeforces Round #716 (Div. 2)

c 풀다가 너무 졸려서 잠깐 침대에 누웠더니 아침이 되어 있었다. 하지만 다음 날 다시 풀어봤는데도 못풀겠어서 결국 풀이를 봤다.

그냥 실력대로 본 것 같다.

A. Perfectly Imperfect Array

배열 a의 원소들 중 하나라도 완전제곱수가 아니면 yes

B. AND 0, Sum Big

전부 and 했을 때 0이 되려면 각 자리마다 적어도 하나는 0이 되게끔 해야한다.

예를 들어 배열의 원소들이 5자리 수라면

 

0 1 1 1 1

1 0 1 0 1

1 1 1 1 0

1 1 0 1 1

.....

이런 모양이 되어야 한다. 그리고 수의 범위는 0에서 2^k-1이므로 배열의 원소들은 k자리 이진수로 생각할 수 있고

원소들의 합이 최대가 되게 하려면 0을 최대한 적은 개수로 배치하면 된다.

따라서 k개의 0을 각 자리마다 하나씩 배치하는 경우의 수 = n^k

C. Product 1 Modulo N

b의 모든 원소들의 곱을 p라고 하면 gcd(p, n) = gcd(p mod n, n) = gcd(1, n) = 1이므로 p는 n과 서로소 관계다.

따라서 b의 모든 원소들은 n과 서로소여야만 한다.

1~n-1에서 n과 서로소인 모든 수들의 곱을 x라고 하자. 이때 x mod n = 1이 된다면 곱했던 모든 수들의 집합이 답이 된다.

하지만 x mod n != 1인 경우, 즉 x mod n = x' (x' != 1) 이라면 위의 집합에서 x'만 빼면 그게 답이 된다.

왜냐하면 gcd(x, n) = gcd(x mod n, n) = gcd(x', n) = 1이기 때문에 x'은 n과 서로소여서 n과의 서로소 집합에 항상 포함되기 때문이다.