📖 문제 개요

문제

양의 정수 $x$와 $n$이 주어졌을 때, $2n+1$개의 정수 $x,x+1,\cdots, x+2n$을 길이 $n$인 두 수열 $A=[A_1,A_2,\cdots,A_n]$과 $B=[B_1,B_2,\cdots,B_n]$, 그리고 하나의 수 $c$로 나누어 다음 수식들이 모두 충족되도록 해야 한다.

$$ \begin{align*} A_1 \,+\, &c = B_1 \\ A_2 \,+\, &c = B_2 \\ &\vdots \\ A_n \,+\, &c = B_n \end{align*}  $$

이때 가능한 서로 다른 $c$의 값의 개수를 구하시오.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 100$)

그다음 줄부터 각각의 테스트 케이스에 대해, 양의 정수 $x$와 $n$이 공백으로 구분되어 한 줄에 주어진다. ($1 \le x,n\le 10^9$)

출력

각각의 테스트 케이스에 대해, 문제의 정답을 한 줄에 출력한다.

예제 입력 1

2
1 3
2 4

예제 출력 1

3
1

✏️ 풀이

만약 $n$의 값이 작았다면, 완전 탐색이나 그리디 등의 방법을 이용하여 푸는 방법이 존재할 듯 하다. 하지만, $n$의 상한이 너무 높은 상황에서 이러한 방법을 사용해 시간 안에 풀어내는 건 좋은 방법이 아니기에, 우리는 다른 방법을 생각해야 한다.

$A_i+c=B_i$가 의미하는 바가 무엇일까? Modular 연산을 이용하면 다음과 같이 바꾸어 쓸 수 있다.

$$ A_i\equiv B_i \pmod{c} $$

뭐 사실 수학적으로 굉장히 고능한 지식은 아니지만, 여기서는 많이 도움이 된다. 즉, 문제를 다음과 같이 바꾸어 해석해 보자.

전체 집합을 $S$라고 하고, $S$의 임의의 원소를 $S_i$($0≤i≤\left| S \right|-1$)라고 하자. 이때, $S$는 다음의 조건을 만족해야 한다.

• $S_i\equiv 0\pmod{c}$를 만족하는 $i$가 홀수 개 존재한다.
• $S_i\equiv x \pmod{c}$($1≤x<c$)를 만족하는 $i$가 짝수 개 존재한다.