P16234 [Lanqiao Cup 2026 NOI Qualifier B] Cyclic Right Shift

All Lanqiao Cup 2026 provincial contest testdata on this site are created by Luogu and may differ from the official data. They are for learning reference only.

Given three integers $N, X, Y$. Please compute how many integer arrays $A$ of length $N$ satisfy the following conditions: 1. Each element $A_i$ in array $A$ satisfies $X \le A_i \le Y$. 2. For any contiguous subarray of $A$, after performing one cyclic right shift operation on it, the new subarray is exactly the same as the original subarray. Cyclic right shift: For a contiguous subarray of length $k$, $[B_1, B_2, \dots, B_k]$, performing one cyclic right shift means transforming it into $[B_k, B_1, B_2, ..., B_{k-1}]$ (i.e., move the last element to the front, and shift the other elements one position to the right in their original order).

The first line contains an integer $T$, indicating the number of test cases. The next $T$ lines each contain three integers $N, X, Y$ separated by spaces.

For each test case, output one line containing an integer, representing the number of arrays $A$ that satisfy the conditions.

### Constraints For $30\%$ of the test cases, $1 \le T \le 20$, $1 \le N \le 100$, $1 \le X, Y \le 100$. For $100\%$ of the test cases, $1 \le T \le 10^3$, $1 \le N \le 10^{18}$, $1 \le X, Y \le 10^{18}$. Translated by ChatGPT 5