No.3168 [Cherry 7th Tune D] Manhole
Problem Visual
▶ Open to reveal the problem visual
Problem Statement
In coordinate space ($xyz$ space), let $\ell$ be the line passing through the origin and the point $(A,B,C)$, and let $\Gamma$ be the surface of the infinite cylinder of radius $1$ with axis $\ell$.
Let $S$ be the area of the region enclosed by the intersection of $\Gamma$ and the $xy$ plane.
Here, with $\pi$ denoting the circle constant, find $\left(\dfrac{S}{\pi} \right)^2 \pmod{998244353}$.
Under the constraints of this problem, the following can be proved.
- The region enclosed by the intersection of $\Gamma$ and the $xy$ plane exists, and its area exists and is finite.
- $\left(\dfrac{S}{\pi} \right)^2$ is a rational number.
Solve $T$ test cases.
Notes
Under the constraints of this problem, it can be proved that there exists a pair of integers $(X,Y)$ satisfying the following.
- $Y$ is not a multiple of $998244353$.
- $Y \times \left(\dfrac{S}{\pi} \right)^2 = X$.
For a pair of integers $X,Y$ satisfying these conditions, there exists a unique integer $Z$ between $0$ and less than $998244353$ such that $$Y \times Z \equiv X \pmod{998244353}$$ so using this integer $Z$, we define $\left(\dfrac{S}{\pi} \right)^2 \pmod{998244353}:=Z$.
Note that there are many possible pairs of integers $(X,Y)$ satisfying the conditions, but $Z$ does not depend on the choice of $X,Y$ and is determined solely by $\left(\dfrac{S}{\pi} \right)^2$.
Constraints
- $1 \leq T \leq 3 \times 10^5$.
- Constraints for each test case
- $0 \leq A < 998244353$.
- $0 \leq B < 998244353$.
- $1 \leq C < 998244353$.
- All inputs are integers.
Input
The input is given from standard input in the following format.$T$
$\textrm{Testcase}_1$
$\textrm{Testcase}_2$
$\vdots$
$\textrm{Testcase}_T$
Each test case is in the following format.
$A$ $B$ $C$
Output
The output consists of $T$ lines. On line $t~(1 \leq t \leq T)$, print the answer for test case $t$ as an integer.
Sample
Sample 1
Input
2 1 2 3 141421356 173205080 223606797
Output
221832080 392186765
- [Test case $1$] $S=\dfrac{\sqrt{14}}{3} \pi$. Therefore, $\left(\dfrac{S}{\pi} \right)^2=\dfrac{14}{9}$. Then, $9 \times \left(\dfrac{S}{\pi} \right)^2=14$, and since $$9 \times 221832080 \equiv 14 \pmod{998244353}$$ we have $\left(\dfrac{S}{\pi} \right)^2 \pmod{9982444353} = 221832080$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun