Codeforces Round #729 (Div. 2)

A. Odd Set (00:02, +)

두 정수를 더해서 홀수를 만드는 방법은 홀수+짝수밖에 존재하지 않는다.

따라서, 각 그룹마다 홀수의 개수와 짝수의 개수가 같다면 Yes이다.

 

B. Plus and Multiply (00:14, +)

1에서 a를 곱하거나 b를 더해 n을 만들 수 있는지 묻는 문제이다.

n을 만들 때에 a를 k번 곱했다고 가정하자. 그렇다면 \( n=a^k+xb \) 꼴로 표현됨을 알 수 있다.

따라서 모든 \( a^k<=n \) 에 대해서 \( n-a^k \) 가 b로 나누어떨어지는지 확인해주면 문제를 \( O(TlogN) \) 에 해결할 수 있다.

 

C. Strange Function (00:43, +)

\( f(i) \) 를 \(i\) 와 서로소인 가장 작은 정수라 할때, \( \sum_{i=1}^N f(i) \) 를 구하는 문제이다.

\( f(i)=x \) 라 하자. 이 때에, \(i\) 는 \( \operatorname{lcm} (1..x-1) \) 의 배수여야 한다. 따라서, \( f(i)=x \) 를 만족하는 \(i\)의 갯수는 \( \frac{n}{ \operatorname{lcm} (1..x-1) } - \frac{n}{ \operatorname{lcm} (1..x) } \) 가 된다. \( \operatorname{lcm} (1..41) > 10^{16} \) 이므로 \(O(40T)\) 정도에 문제를 해결할 수 있다.