[BOJ 30913] 위수는 쿼리입니까?

오랜만에 찾아온 백준 포스팅이에요~! 7.15에 군대에 가는데 그 전에 루비를 찍고 가려고 열심히 문제 풀고 있습니다!

최근에 클8도 따고 해서 루비까지 남은 레이팅은 21점!!! 남은 레이팅은 제가 좋아하는 정수론으로 채울겁니다!

아 정수론 오랜만에 하니까 감이 좀 떨어진듯 하네요;;

 

일단 각 쿼리를 각각 처리해봅시다. 

 

첫 번쨰 쿼리

$N=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{t}^{r_{t}}$가 $N$의 소인수분해라고 합시다. 주어진 $a$에 대하여 $a^{e}\equiv 1\pmod{N}$을 만족하는 최소의 $e$를 찾기 위해서는 먼저 $\gcd(a,N)=1$이어야 합니다. $\gcd(a,N)=1$을 가정해두고 논의를 진행합시다. $a$의 위수를 찾기 위해서 다음 렘마를 사용합니다. 

Lemma. $\text{ord}_{p_{i}^{r_{i}}}(a)=e_{i}$라고 두면 $\text{LCM}(e_{1},\cdots,e_{t})=\text{ord}_{N}(a)$

(proof) $k= \text{LCM}(e_{1},\cdots,e_{t})$, $e= \text{ord}_{N}(a)$로 둡시다. 각 $e_{i}$에 대하여 $e_{i}|k$이기 때문에 $a^{k}\equiv 1\pmod{p_{i}^{r_{i}}}$가 됩니다. CRT에 의해 $a^{k}\equiv 1\pmod{N}$이고 위수의 정의로 인해 $e|k$입니다. $a^{e}\equiv 1\pmod{N}$이 정의에 의해 성립하고 이는 곧 $a^{e}\equiv 1\pmod{p_{i}^{r_{i}}}$임을 의미합니다. 위수의 정의에 의해 모든 $i$에 대하여 $e_{i}|e$입니다. 이는 곧 $k|e$를 의미합니다. 따라서 $k=e$입니다. $\blacksquare$

 

따라서 우리는 $p_{i}^{r_{i}}$들에 대해서 $a$의 위수를 구해주면 됩니다. $p^{r}$에 대하여 $a$의 위수를 구하는 방법을 알아봅시다! $a$의 위수는 $\phi(p^{r})$을 나눈다는 것은 잘 알려진 사실입니다. $\phi(p^{r})=q_{1}^{s_{1}}q_{2}^{s_{2}}\cdots q_{k}^{s_{k}}$가 $\phi(p^{r})$의 소인수분해라고 합시다. 예를 들어$a^{\phi(p^{r})/q_{1}} \equiv 1\pmod{p^{r}}$이고 $a^{\phi(p^{r})/q_{1}^{2}} \not\equiv 1\pmod{p^{r}}$이라면 어떨까요? 그럼 $v_{q_{1}}(\text{ord}_{p^{r}}(a))= s_{1}-1$입니다. 이런 방식으로 $a$의 위수가 가지는 소인수들을 찾아낼 수 있습니다. 이제 $p_{i}^{r_{i}}$들에 대해 구한 $a$의 위수를 최소공배수로 합쳐주기만 하면 끝입니다!

 

두 번째 쿼리 

이번에는 위수가 $e$가 되는 정수 $a$를 찾아야 합니다. 우리는 각 $p_{i}^{r_{i}}$에 대한 $a$의 위수의 최소공배수가 $e$가 된다는 사실을 알고 있습니다. $e$를 소인수분해 한 것이 $e=q_{1}^{s_{1}}\cdots q_{k}^{s_{k}}$라고 둡시다. 모든 $j$에 대하여 적어도 하나의 $i$에 대해서 $q_{j}^{s_{j}}|\phi(p_{i}^{r_{i}})$를 만족해야합니다. 그렇지 않으면 $0$을 리턴합니다.(즉, 답이 존재하지 않습니다.) 위와 같이 각 $i$에 대해서 할당된 $q_{j}^{s_{j}}$들의 곱을 $e_{i}$라고 합시다. 만약 $i$에 대해 할당된 값이 없다면 $e_{i}=1$이라고 합시다. 이때 $\text{LCM}(e_{1},\cdots,e_{t})=e$가 됩니다. $p_{i}^{r_{i}}$에 대하여 위수가 $e_{i}$가 되는 수는 간단히 원시근 $g$에 대하여 $g^{\phi(p_{i}^{r_{i}})/e_{i}} \pmod{p_{i}^{r_{i}}}$입니다.(원시근 $g$가 존재할 필요충분조건은 $n=2,4,p^{k},2p^{k}$ $p$는 홀수인 소수입니다.) 따라서 $g^{\phi(p_{i}^{r_{i}})/e_{i}} \pmod{p_{i}^{r_{i}}} $이 값들을 계산해두고 CRT로 합친 결과인 $a\pmod{N}$이 답이 됩니다. 

하지만 만약 $p_{i}^{r_{i}}=2^{r}$이라면 어떨까요? $r> 2$이라면 원시근이 존재하지 않습니다. $\pmod{2^{r}}$에 대해서 위수가 $e$인 수 $a$를 찾는다고 해봅시다. 다음과 같은 사실이 있습니다. 

Lemma. $\mathbb{Z}^{\times}_{2^{r}}\cong \mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2^{r-2}\mathbb{Z}$

일단 $\phi(2^{r})=2^{r-1}$이기 때문에 위수 $e$는 반드시 $2$의 거듭제곱이어야 합니다. 또, 위 보조정리에 의해 위수는 최대 $2^{r-2}$입니다. 또 그 위수를 가지는 수는 $3$입니다. 그럼 위수가 $2^{r-3}$이 되는수는 $9$로 두면 되겠죠? 이런 방식으로 $a$를 찾아내면 됩니다! 

$2^{r}$의 등장으로 인해 $e_{i}$를 설정하는 로직 역시 살짝 변경되어야 합니다. $\phi(2^{r})$의 값은 실제로 $2^{r-1}$이지만 그냥 $2^{r-2}$로 치고 위 로직을 진행합시다. 또한, $2^{r}$의 원시근은 존재하지 않지만 $3$이라고 칩시다. 

이제 홀수인 소수의 거듭제곱에 대하여 $g$를 구할 수 있어야겠군요! $g$는 첫 번째 쿼리를 이용하면 됩니다. $N=p_{i}^{r_{i}}$라고 두고 $a$를 $2$부터 $N-1$까지 대입해가며 위수를 찾아냅니다. 이때 위수가 $\phi(N)$이 된다면 그 수는 $g$ 즉, 원시근이 됩니다. 

 

세 번째 쿼리

먼저 $\pmod{p^{r}}$($p$는 홀수)에서 위수가 $e$인 개수를 찾아봅시다. 원시근 $g$에 대하여 $g^{ke}\equiv 1\pmod{p^{r}}$가 되는 $k$의 개수를 찾아봅시다. 이때 $\phi(p^{r})|ke$이며 $\frac{\phi(p^{r})}{e}|k$입니다. $k$의 범위는 $1\le k\le \phi(p^{r})$임을 고려하면 후보는 $\{\frac{a\phi(p^{r})}{e}|1\le a\le e\}$입니다. 만약 $a$가 $e$와 서로소가 아니라면 $g=\gcd(a,e)>1$이고 $g^{ \frac{(a/g)\phi(p^{r})}{(e/g)} }$의 위수는 $e/g$가 됩니다. $a$와 $e$가 서로소라고 두고 $g^{ \frac{a\phi(p^{r})}{e}}$의 위수가 $d|e$라고 가정합시다. 이때 $\phi(p^{r})| \frac{da\phi(p^{r})}{e}$이 성립하고 아는 $e|da$임을 의미합니다. $a$와 $e$가 서로소이므로 $e|d$입니다. 즉, $d=e$입니다. 따라서 $k\in \{\frac{a\phi(p^{r})}{e}|1\le a\le e \land (a,e)=1\}$이 성립합니다. 즉, $k$의 개수는 $\phi(e)$입니다. 

이제 $\pmod{2^{r}}$ 인 경우에 대해서 봅시다. $r\le 2$인 경우는 원시근이 있는 경우와 동일하기 때문에, $r>2$인 경우만 봅시다. 이전에 $3$의 위수가 $2^{r-2}$라는 것을 알아냈습니다. 그럼 $3$의 거듭제곱이 아닌 나머지 $2^{r-2}$개의 수들은 어디에 있을까요? 그들은 사실 $-3^{a}$ 꼴을 가집니다. 이는 $3$의 거듭제곱 중에 $-1$이 존재하지 않음을 보이면 증명할 수 있습니다. 

(proof) $3^{k}\equiv -1\pmod{2^{r}}$이라고 가정하자. 그럼 $3^{2k}\equiv 1\pmod{2^{r}}$이며 $2^{r-2}|2k\implies 2^{r-3}|k$이다. $1\le k\le 2^{r-2}$이기 때문에 $k=2^{r-3},2^{r-2}$ 중 하나이다. $k=2^{r-2}$인 경우 모순이고 $k=2^{r-3}$인 경우를 가정하자. $r=3$인 경우 문제가 될 수 있으니 $r>3$을 먼저 가정하자. 그럼 $3^{2^{r-3}}\equiv -1\pmod{2^{r}}$이다. 이것은 또, $3^{2^{r-3}} \equiv -1\pmod{2^{r-1}}$과 동일한 의미를 가진다. $r-1>2$이므로 $3^{2^{r-3}}\equiv 1\pmod{2^{r-1}}$이다. $2^{r-1}\nmid 2$이므로 모순이며 $-1$은 $3$의 거듭제곱이 아니다. $r=3$인 경우 직접 대입해서 계산해보면 아니라는 것을 알 수 있다. $\blacksquare$ 

먼저 $3$의 거듭제곱인 친구들의 위수를 알아봅시다. $n$이 홀수인 경우 $3^{n}$의 위수는 $2^{r-2}$입니다. $n$이 짝수인 경우 $n=2^{t}n'(2\nmid n')$일때 위수는 $2^{r-2-t}$입니다. 나머지 $-3^{a}$ 꼴 수들을 봅시다. 어차피 이들의 위수는 $1$이 아니고 항상 $2$의 거듭제곱이므로 결국 $-1$이 사라지게 되어서 $3$의 거듭제곱인 친구들의 위수와 동일해집니다. 하지만 $-3^{2^{r-2}}=-1$의 위수는 2로 $3^{2^{r-2}}=1$의 위수 1과 다릅니다. 

정리하자면, 위수가 $2^{r-2}$인 것은 총 $2^{r-2}$개. 위수가 $2^{r-2-t}$인 것은 $2^{r-2-t}$개 이고 위수가 2일 때에는$-1$때문에 개수에 +1을 해주어야 합니다.  (함수 $add(e)$를 정의하는데 $e=2$이면 값이 1이고 그렇지 않은 경우 0입니다.)

 

$\pmod{N}$에 대해서 위수가 $e$인 개수를 찾는다고 할 때 먼저 최소공배수가 $e$가 되는 $(e_{1},\cdots,e_{t})$들을 찾습니다. 각 $\pmod{p_{i}^{r_{i}}}$에 대하여 위수가 $e_{i}$인 수를 하나 찾았다고 합시다. 이것을 CRT로 합치면 $\pmod{N}$에서의 위수가 $e$인 수 1개가 나옵니다. 각 $\pmod{p_{i}^{r_{i}}}$에 대하여 위수가 $e_{i}$인 수가 $\phi(e_{i})$개 있기 때문에 아래가 우리가 구해야하는 값입니다.

\[\sum_{\text{LCM}(e_{1},\cdots,e_{t})=e}\phi(e_{1})\cdots \phi(e_{t}) \ \ \ \ \ \ \cdots (1)\]

이때 $\phi$ 함수는 곱셈적 함수라는 것과 각 $e_{i}|\phi(p_{i}^{r_{i}})$임을 이용합시다. $S$를 모든 $i$에 대하여$\phi(p_{i}^{r_{i}})$의 소인수의 집합이라고 합시다. 그럼 (1)은 다음과 같이 바꿀수 있습니다.

\[\sum_{\text{LCM}(e_{1},\cdots,e_{t})=e }\prod_{q\in S}\phi(q^{v_{q}(e_{1})})\cdots \phi(q^{v_{q}(e_{t})})\]

\[\prod_{q\in S} \sum_{\text{LCM}(e_{1},\cdots,e_{t})=e }\phi(q^{v_{q}(e_{1})})\cdots\phi(q^{v_{q}(e_{t})})\]

\[\prod_{q\in S} \sum_{\begin{gather}\text{max}(f_{1},\cdots,f_{t})=v_{q}(e) \\ \forall i\ f_{i}\le v_{q}(\phi(p_{i}^{r_{i}})) \end{gather}}\phi(q^{f_{1}})\cdots\phi(q^{f_{t}})\]

\[\prod_{q\in S} \left[ \sum_{\forall i\ f_{i}\le \text{min}(v_{q}(e), v_{q}(\phi(p_{i}^{r_{i}}) ))}\phi(q^{f_{1}})\cdots\phi(q^{f_{t}}) - \sum_ {\forall i\ f_{i}\le \text{min}(v_{q}(e) - 1, v_{q}(\phi(p_{i}^{r_{i}})) )} \phi(q^{f_{1}})\cdots\phi(q^{f_{t}})  \right] \]

\[\prod_{q\in S} \left[ \sum_{\forall i\ f_{i}\le \text{min}(v_{q}(e), v_{q}(\phi(p_{i}^{r_{i}}) ))}\prod_{1\le i\le t}\phi(q^{f_{i}}) - \sum_ {\forall i\ f_{i}\le \text{min}(v_{q}(e) - 1, v_{q}(\phi(p_{i}^{r_{i}})) )} \prod_{1\le i\le t}\phi(q^{f_{i}})  \right] \]

\[\prod_{q\in S} \left[ \prod_{1\le i\le t} \sum_{f_{i}\le \text{min}(v_{q}(e), v_{q}(\phi(p_{i}^{r_{i}}) ))}\phi(q^{f_{i}}) - \prod_{1\le i\le t} \sum_ {f_{i}\le \text{min}(v_{q}(e) - 1, v_{q}(\phi(p_{i}^{r_{i}})) )} \phi(q^{f_{i}})  \right] \]

\[\prod_{q\in S} \left[ \prod_{1\le i\le t} q^{ \text{min}(v_{q}(e), v_{q}(\phi(p_{i}^{r_{i}})) ) }- \prod_{1\le i\le t} q^{ \text{min}(v_{q}(e) - 1, v_{q}(\phi(p_{i}^{r_{i}}) )) }  \right] \]

\[\prod_{q\in S} \left[ q^{\sum_{1\le i\le t} \text{min}(v_{q}(e), v_{q}(\phi(p_{i}^{r_{i}})) ) }-  q^{ \sum_{1\le i\le t} \text{min}(v_{q}(e) - 1, v_{q}(\phi(p_{i}^{r_{i}}) )) }  \right] \]

짠 이제 위 식만 계산해주면 끝! 다만, $p_{1}^{r_{1}}=2^{r_{1}}(r_{1} > 2)$인 경우 계산이 달라진다. 그럼 문제를$N'=p_{2}^{r_{2}}\cdots p_{t}^{r_{t}}$와 $2^{r_{1}}$에 대해서 위수를 구한 뒤 그 최소공배수가 $e$가 되게 하는 것으로 바꾸자. $e=2^{k}e'(2\nmid e')$이라고 가정하자. 이제 최소공배수가 $e$가 되게 하는 위수들의 조합을 찾아보자. $2^{r_{1}}$의 위수들은 $1,2,2^{2},\cdots,2^{r_{1}-2}$까지이다. 이때 $\text{LCM}(2^{a},x)=e(a<k)$를 만족시키는 $x$는 $e$ 뿐이다. $a>k$인 경우는 불가능하다. $a=k$인 경우 가능한 $x$는 $e', 2e', 2^{2}e',\cdots,2^{k}e'$이다. $N'$에 대하여 위수 $e$의 개수를 $g(e)$라는 함수로 정의할 때, 실제 $N$에 대하여 위수 $e$의 개수는 다음과 같다.

\[\sum_{a=0}^{\text{min}(k-1,r-2)}(2^{a}+add(2^{a}))g(e)+[k\le r-2] \sum_{b=0}^{k}(2^{k}+add(2^{k}))g(2^{b}e')\]

\[g(e)(2^{ \text{min}(k-1,r-2) +1}-1+add(*))+(2^{k}+add(2^{k}))+a [k\le r-2] \sum_{b=0}^{k}g(2^{b}e')\]

함수 $g$의 값은 위에서 했던 방법으로 쉽게 계산할 수 있다. 

 

네 번째 쿼리

$C_{i,e_{i}}$를 $\pmod{p_{i}^{r_{i}}}$에서 위수를 $e_{i}$로 가지는 수들의 집합이라고 하자. 우리가 구해야하는 것은

\[\sum_{\text{LCM}(e_{1},\cdots,e_{t})=e}\sum_{(a_{1},\cdots,a_{t})\in C_{1,e_{1}}\times \cdots C_{t,e_{t}}} \text{CRT}(a_{1},\cdots,a_{t}) \pmod{N}\]

$\text{CRT}$ 함수의 의미는 함수의 인자들을 CRT를 이용해서 $\pmod{N}$에서 값을 구하자는 것이다. 문제를 단순화시키기 위해서 이 값을 $\pmod{p_{i}^{r_{i}}}$에서 구해보자. 그럼 위 식은 

\[\sum_{\text{LCM}(e_{1},\cdots,e_{t})=e}\sum_{(a_{1},\cdots,a_{t})\in C_{1,e_{1}}\times \cdots C_{t,e_{t}}} a_{i} \pmod{p_{i}^{r_{i}}}\]

\[\sum_{\text{LCM}(e_{1},\cdots,e_{t})=e}\left[\prod_{j\ne i}|C_{j,e_{j}}| \right]\sum_{a_{i}\in C_{i,e_{i}}} a_{i} \pmod{p_{i}^{r_{i}}}\]

$N$이 $8$로 나누어 떨어지지 않는다고 하자. 

\[\sum_{\text{LCM}(e_{1},\cdots,e_{t})=e}\left[\prod_{j\ne i}\phi(e_{j}) \right]\sum_{a_{i}\in C_{i,e_{i}}} a_{i} \pmod{p_{i}^{r_{i}}}\]

이제 가장 안쪽의 합을 계산해보자. 기호를 단순화시켜서 $C(e)$를 $\pmod{p^{r}}$에서 위수가 $e$인 수의 집합이라고 하자. 그럼 앞의 논의에 의해서 우리가 계산해야 할 것은, 원시근을 $g$라고 두면

\[\sum_{a\in C(e)}a =\sum_{1\le k\le e}[\text{gcd}(k,e)=1] g^{k\frac{\phi(p^{r})}{e}} \pmod{p^{r}}\]

뫼비우스 inversion을 사용하면

\[\sum_{s|e}\mu(s)\sum_{k=1}^{e/s}g^{k\frac{s\phi(p^{r})}{e}} \pmod{p^{r}}\ \ \ \ \ \ \cdots (2)\]

안쪽의 합은 등비수열의 합이기에 $\frac{ g^{\phi(p^{r})} -1}{ g^{\frac{s\phi(p^{r})}{e}}-1}$라고 둘 수 있다. 분자가 자명하게 $0$이기에 그냥 0이라고 단정지을 수 있으나 분모가 $p$의 배수인 경우 저 값이 $0$이 아닐 수 있다. 분모가 $p$의 배수인 경우를 알아보자. $ g^{\frac{s\phi(p^{r})}{e}}\equiv 1\pmod{p}$에서 $p^{r}$의 원시근은 $p$의 원시근임을 이용하면 $(p-1)|\frac{s}{e}\phi(p^{r})$ 을 얻는다. $s|e$이므로 $e=as$라고 두자. 그럼 $(p-1)|(p-1)\frac{p^{r-1}}{a}$가 된다. 즉, $a=1,p,\cdots,p^{r-1}$ 중 하나이면 분모자 $p$의 배수가 된다. $a=p^{s}(0\le s \le r-1)$이라고 두자($a|e$역시 만족해야한다.). 그럼 $g^{\frac{s\phi(p^{r})}{e}}\equiv 1\pmod{p^{r-s}}$이므로 $ g^{\frac{s\phi(p^{r})}{e}}= \alpha p^{r-s} + 1$이라고 두자. 이제 계산하는 값은

\[\sum_{k=1}^{p^{s}} g^{\phi(r-s)k}=(\alpha p^{r-s}+1)\frac{1}{\alpha p^{r-s}}(\cdots + \frac{p^{s}(p^{s}-1)}{2}\alpha^{2}p^{2r-2s}+p^{s}\alpha p^{r-s}) \pmod{p^{r}} \equiv p^{s}\pmod{p^{r}}\]

$a$가 저 중에 하나가 아닌 경우는 항상 $0$이다. 따라서 (2)는

\[\sum_{s=0}^{\text{min}(v_{p}(e), r-1)} \mu(e/p^{s})p^{s} \pmod{p^{r}}\]

위 값을 $h(e)$로 정의하여 함수 $h$를 정의하자. 서로소인 정수 $a,b$에 대하여 $h(ab)$를 계산할 것이다. $p\nmid ab$인 경우 $h(ab)\equiv \mu(ab)\equiv \mu(a)\mu(b)\equiv h(a)h(b)\pmod{p^{r}}$이다. $p|ab$인 경우, 일반성을 잃지 않고 $p|a$, $p\nmid b$라고 가정하면 $h(ab)\equiv \mu(b)h(a)\equiv h(b)h(a)\pmod{p^{r}}$이다. 또한, $h(1)\equiv 1\pmod{p^{r}}$이기에 $h$는 곱셈적 함수이다. 이렇게 되면 세 번째 쿼리를 처리했던 것과 비슷하게 계산을 해줄 수 있다. 세 번쨰 쿼리에 사용했던 식을 보자. 그 떄 인덱스가 $i$인 경우만 함수를 $\phi$대신 $h$로 바꾸면 된다. 다음과 같이 말이다.

\[\prod_{q\in S} \left[ \left[ \sum_{f_{i}\le \text{min}(v_{q}(e), v_{q}(h(p_{i}^{r_{i}}) ))}h(q^{f_{i}}) \right]\prod_{j\in[1,t]\backslash i} \sum_{f_{j}\le \text{min}(v_{q}(e), v_{q}(\phi(p_{j}^{r_{j}}) ))}\phi(q^{f_{j}}) -  \left[\sum_{f_{i}\le \text{min}(v_{q}(e)-1, v_{q}(h(p_{i}^{r_{i}}) ))}h(q^{f_{i}}) \right]\prod_{j\in[1,t]\backslash i} \sum_{f_{j}\le \text{min}(v_{q}(e)-1, v_{q}(\phi(p_{j}^{r_{j}}) ))}\phi(q^{f_{j}}) \right] \]

만약 $q\ne p_{i}$라면 $\sum_{k=0}^{T} h(q^{k}) \in \{0,1\}$이며 $T=0$일 때 $1$이고 $T\ge 1$일 때 $0$입니다. 만약 $q=p_{i}$라고 하자. $k=0$인 경우 안쪽의 합은 1이다. $0<k\le r_{i}-1$인 범위에서는 안쪽의 합이 $p^{k}-p^{k-1}$이다. $k=r_{i}$인 경우 안쪽의 합은 $-p^{r_{i}-1}$이다. $k>r_{i}$인 경우 안쪽의 합은 $0$이다. 이를 이용해서 $h$를 계산하자. 우리가 계산해야 할 것은 아래와 같다. 

\[\prod_{q\in S} \left[ \left[ \sum_{f_{i}\le \text{min}(v_{q}(e), v_{q}(\phi(p_{i}^{r_{i}}) ))}h(q^{f_{i}}) \right] q^{\sum_{j\in [1,t]\backslash i} \text{min}(v_{q}(e), v_{q}(\phi(p_{j}^{r_{j}})) ) } - \left[\sum_{f_{i}\le \text{min}(v_{q}(e)-1, v_{q}(\phi(p_{i}^{r_{i}}) ))}h(q^{f_{i}}) \right] q^{\sum_{j\in [1,t]\backslash i} \text{min}(v_{q}(e)-1, v_{q}(\phi(p_{j}^{r_{j}})) ) } \right] \]

우리는 지금까지 $N$이 8의 배수가 아닌 경우를 생각했습니다. 그 이유는 $N$의 소인수 중에 2가 있으면 $2^{r}|N$이 원시근을 가지길 바랬기 때문입니다. $N$이 8의 배수인 경우에는 세 번째 쿼리와 마찬가지로 $N=2^{r}N'(2\nmid N')$으로 쪼갠 뒤에 다음 문제를 풀면 됩니다. 이때 $C_{1,e_{1}}$은 $\pmod{2^{r}}$에서 위수가 $e_{1}$인 수들의 집합이고 $C_{2,e_{2}}$는 $\pmod{N'}$에서 위수가 $e_{2}$인 수들의 집합입니다. 

\[\sum_{\text{LCM}(e_{1},e_{2})=e} \sum_{(a_{1},a_{2})\in C_{1,e_{1}}\times C_{2,e_{2}}} CRT(a_{1},a_{2})\pmod{N}\]

$\pmod{2^{r}}$에서 위수가 $e$인 수들의 합을 구해봅시다. $e$는 $\{1,2,\cdots,2^{r-2}\}$ 중에 1개 입니다. $e=1$인 경우 자명하게 합이 1입니다. $e=2^{r-2-s}(r-2>s)$를 가정합시다. $3^{2^{s}t}$와 $-3^{2^{s}t}$($t$는 홀수)들은 모두 위수가 $e>2$인 수이기 때문에 더하면 $0$이 됩니다. $e=2$이면 대칭성과 따로 존재하는 $-1$로 인해 더한 값이 $-1$이 됩니다. 만약 $e>2$이면, 

\[\sum_{\text{LCM}(e_{1},e_{2})=e} |C_{2,e_{2}}| \sum_{a_{1}\in C_{1,e_{1}}} a_{1} \equiv |C_{2,e}|-|C_{2,e}|\equiv - \pmod{2^{r}}\]

이고, $e=2$이면, 위와 같은 계산법으로 $-|C_{2,e/2}| \pmod{2^{r}}$이 됩니다. $e=1$이면, $|C_{2,e}| \pmod{2^{r}} $가 됩니다.

$\pmod{N}$에 대해서는 세 번째 쿼리와 같은 방식으로 다음을 얻습니다. $v_{2}(e)=k$라고 두고 $g(e)$를 $N'$에 대한 네 번째 쿼리의 답이라고 할 때 정답은 아래와 같습니다. 

\[\sum_{a=0}^{\text{min}(k-1,r-2)}(2^{a}+add(2^{a}))g(e)+[k\le r-2] \sum_{b=0}^{k}(2^{k}+add(2^{k}))g(2^{b}e')\]

\[g(e)(2^{ \text{min}(k-1,r-2) +1}-1+add(*))+(2^{k}+add(2^{k}))+a [k\le r-2] \sum_{b=0}^{k}g(2^{b}e')\]

 

아래에는 이것을 구현한 코드가 있습니다.

# 코드 보기

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
vector<pair<ll, ll> > fac_N;
vector<vector<pair<ll, ll> > > fac_ppe;
vector<ll> phi_pe;
vector<ll> pe;
vector<ll> prim_pe;
ll phi_N = 1;
 
vector<pair<ll, ll> > fac_N_n2;
vector<vector<pair<ll, ll> > > fac_ppe_n2;
vector<ll> phi_pe_n2;
vector<ll> pe_n2;
ll phi_N_n2 = 1;
 
ll fpow(ll n, ll k, ll mod){
    ll s = 1;
    for(;k;k >>= 1){
        if(mod){
            if(k & 1) s = (__int128) s * n % mod;
            n = (__int128) n * n % mod;
        }
        else{
            if(k & 1) s = s * n;
            n = n * n;
        }
    }
    return s;
}
 
ll miller(ll n,ll a){
    ll t=n-1;
    while(t%2==0) if(fpow(a,t/=2,n)==n-1) return 1;
    t=fpow(a,t,n);
    return t==n-1 || t==1;
}
 
ll prime(ll n){
    if(n==1) return 0;
    int m=12,i;
    ll a[12]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for(i=0;i<m;i++){
        if(a[i]==n) return 1;
        if(!miller(n,a[i])) return 0;
    }
    return 1;
}
 
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
 
ll rf(ll x,ll n){
    return ((__int128)x*x+13)%n;
}
 
ll pollard_rho(ll n){
    ll x=2,y=2,t=1,c=13;
    if(prime(n)) return n;
    if(n%2==0) return 2;
    while(t==1 || t==n){
        x=rf(x,n);
        y=rf(rf(y,n),n);
        t=gcd(x>y?x-y:y-x,n);
        if(t==n) x=y=rand()%n;
    }
    return prime(t)? t:pollard_rho(t);
}
 
void factorize(vector<pair<ll, ll> > &s, ll n){
    if(n == 1) return;
    ll r;
    while(n-1){
        r = pollard_rho(n);
        n /= r;
        s.push_back({r, 1});
    }
    sort(s.begin(), s.end());
    
    vector<pair<ll, ll> > q;
    q.push_back({s[0].first, 1});
    for(int i = 1;i < s.size();i++){
        if(q[q.size() - 1].first == s[i].first){
            q[q.size() - 1].second++;
        }
        else q.push_back({s[i].first, 1});
    }
    s = q;
}
 
ll solve0(ll a, int idx){ //원시근 찾기  
    if(gcd(a, pe[idx]) > 1) return 0;
    ll ret = 1;
    for(int i = 0;i < fac_ppe[idx].size();i++){
        ll t = 1, cnt = 0;
        for(int k = 0;k < fac_ppe[idx][i].second;k++){
            t *= fac_ppe[idx][i].first;
            cnt++;
            if(fpow(a, phi_pe[idx] / t, pe[idx]) != 1){
                cnt--;
                break;
            }
        }
        ret *= fpow(fac_ppe[idx][i].first, fac_ppe[idx][i].second - cnt, 0);
    }
    return ret;
}
 
ll solve1(ll a, ll N){
    if(gcd(a, N) > 1) return 0;
    ll ret = 1;
    for(int i = 0;i < fac_N.size();i++){
        vector<pair<ll, ll> > fac_ppe;
        factorize(fac_ppe, phi_pe[i]);
        ll ei = 1;
        for(int j = 0;j < fac_ppe.size();j++){
            ll t = 1, cnt = 0;
            for(int k = 0;k < fac_ppe[j].second;k++){
                t *= fac_ppe[j].first;
                cnt++;
                if(fpow(a, phi_pe[i] / t, pe[i]) != 1){
                    cnt--;
                    break;
                }
            }
            ei *= fpow(fac_ppe[j].first, fac_ppe[j].second - cnt, 0);
        }
        ret = ret * ei / gcd(ret, ei);
    }
    return ret;
}
 
ll find_prim(int idx){ //existence guaranted & if pe=2^{k} just return 3
    if(pe[idx] % 2 == 0) return 3 % pe[idx];
    for(int i = 1;i < pe[idx];i++){
        ll ord = solve0(i, idx);
        if(ord == phi_pe[idx]) return i;
    }
    return -1;
}
 
ll CRT(vector<ll> &a, ll N){
    ll ret = 0;
    for(int i = 0;i < pe.size();i++){
        ll div = N / pe[i];
        ll tmp = (__int128)a[i] * div %(__int128) N * fpow(div, phi_pe[i] - 1, pe[i]) % N;
        ret = (ret + tmp) % N;
    }
    return ret;
}
 
ll CRT_n2(vector<ll> &a, ll N){
    ll ret = 0;
    for(int i = 0;i < pe_n2.size();i++){
        ll div = N / pe_n2[i];
        ll tmp = (__int128)a[i] * div % (__int128)N * fpow(div, phi_pe_n2[i] - 1, pe_n2[i]) % N;
        ret = (ret + tmp) % N;
    }
    return ret;
}
 
ll solve2(ll e, ll N){
    vector<ll> save(phi_pe.begin(), phi_pe.end());
    if(phi_N % e) return 0;
    vector<pair<ll, ll> > fac_e;
    factorize(fac_e, e);
    for(int i = 0;i < fac_e.size();i++){
        ll q = fac_e[i].first;
        ll qe = fpow(q, fac_e[i].second, 0);
        ll jd = -1;
        for(int j = 0;j < phi_pe.size();j++){
            if(pe[j] % 8 == 0 && qe % 2 == 0){
                if((phi_pe[j] / 2) % qe) continue;
                jd = j;
                save[j] = save[j] / 2 / qe;
                break;
            }
            if(phi_pe[j] % qe) continue;
            jd = j;
            save[j] = save[j] / qe;
            break;
        }
        if(jd == -1) return 0;
    }
    
    vector<ll> a;
    for(int i = 0;i < save.size();i++){
        a.push_back(fpow(prim_pe[i], save[i], pe[i]));
    }
    return CRT(a, N);
}
 
ll get_v(ll p, ll n){
    ll cnt = 0;
    while(n % p == 0){
        n /= p;
        cnt++;
    }
    return cnt;
}
 
ll g(ll e, ll N){
    if(phi_N % e) return 0;
    
    set<ll> primes;
    for(int i = 0;i < fac_ppe.size();i++){
        for(int j = 0;j < fac_ppe[i].size();j++){
            primes.insert(fac_ppe[i][j].first);
        }
    }
    ll ret = 1;
    for(ll pri: primes){
        ll up = 1, dn = 1;
        ll f = get_v(pri, e);
        for(int i = 0;i < phi_pe.size();i++){
            ll up_T = min(f, get_v(pri, phi_pe[i]));
            ll dn_T = min(f - 1, get_v(pri, phi_pe[i]));
            up *= fpow(pri, up_T, 0);
            if(dn_T >= 0) dn *= fpow(pri, dn_T, 0);
            else dn = 0;
        }
        ret *= up - dn;
    }
    return ret;
}
 
ll g_n2(ll e, ll N){ //only when N is odd
    if(phi_N_n2 % e) return 0;
    
    set<ll> primes;
    for(int i = 0;i < fac_ppe_n2.size();i++){
        for(int j = 0;j < fac_ppe_n2[i].size();j++){
            primes.insert(fac_ppe_n2[i][j].first);
        }
    }
    ll ret = 1;
    for(ll pri: primes){
        ll up = 1, dn = 1;
        ll f = get_v(pri, e);
        for(int i = 0;i < phi_pe_n2.size();i++){
            ll up_T = min(f, get_v(pri, phi_pe_n2[i]));
            ll dn_T = min(f - 1, get_v(pri, phi_pe_n2[i]));
            up *= fpow(pri, up_T, 0);
            if(dn_T >= 0) dn *= fpow(pri, dn_T, 0);
            else dn = 0;
        }
        ret *= up - dn;
    }
    return ret;
}
 
ll solve3(ll e, ll N){
    ll pow2_e = get_v(2, e);
    ll pow2_N = get_v(2, N);
    
    ll e_n2 = e;
    while(e_n2 % 2 == 0) e_n2 /= 2;
    ll N_n2 = N;
    while(N_n2 % 2 == 0) N_n2 /= 2;
    
    if(N / N_n2 <= 4) return g(e, N);
    
    ll add = 0;
    if(1 <= min(pow2_e - 1, pow2_N - 2)) add = 1;
    ll ret = g_n2(e, N_n2) * (fpow(2, min(pow2_e - 1, pow2_N - 2) + 1, 0) - 1 + add);
    ll ret2 = 0, tmp = 1;
    for(int i = 0;i <= pow2_e && pow2_e <= pow2_N - 2;i++){
        ret2 += g_n2(tmp * e_n2, N_n2);
        tmp *= 2;
    }
    ll add2 = 0;
    if(pow2_e == 1) add2 = 1;
    ret2 *= fpow(2, pow2_e, 0) + add2;
    return ret + ret2;
}
 
ll h(ll q, ll p, ll e_p, ll T){
    if(q != p){
        if(T == 0) return 1;
        return 0;
    }
    if(T >= e_p) return 0;
    return fpow(p, T, 0);
}
 
ll g4_n2(ll e, ll N){
    if(phi_N_n2 % e) return 0;
    vector<ll> a;
    set<ll> primes;
    for(int i = 0;i < fac_ppe_n2.size();i++){
        for(int j = 0;j < fac_ppe_n2[i].size();j++){
            primes.insert(fac_ppe_n2[i][j].first);
        }
    }
    
    for(int i = 0;i < pe_n2.size();i++){
        ll ret = 1;
        for(ll pri: primes){
            ll ve = get_v(pri, e);
            ll up = 1, dn = 1;
            for(int j = 0;j < pe_n2.size();j++){
                ll up_T = min(ve, get_v(pri, phi_pe_n2[j]));
                ll dn_T = min(ve - 1, get_v(pri, phi_pe_n2[j]));
                if(dn_T < 0) dn = 0;
                if(i == j){
                    up =(__int128) up * h(pri, fac_N_n2[i].first, fac_N_n2[i].second, up_T) % pe_n2[i];
                    if(dn_T >= 0) dn =(__int128) dn * h(pri, fac_N_n2[i].first, fac_N_n2[i].second, dn_T) % pe_n2[i];
                }
                else{
                    up =(__int128) up * fpow(pri, up_T, pe_n2[i]) % pe_n2[i];
                    if(dn_T >= 0) dn =(__int128) dn * fpow(pri, dn_T, pe_n2[i]) % pe_n2[i];
                }
            }
            ret =(__int128) ret * (((up - dn) % pe_n2[i] + pe_n2[i]) % pe_n2[i]) % pe_n2[i];
        }
        a.push_back(ret);
    }
    return CRT_n2(a, N);
}
 
ll g4(ll e, ll N){
    if(phi_N % e) return 0;
    vector<ll> a;
    set<ll> primes;
    for(int i = 0;i < fac_ppe.size();i++){
        for(int j = 0;j < fac_ppe[i].size();j++){
            primes.insert(fac_ppe[i][j].first);
        }
    }
    
    for(int i = 0;i < pe.size();i++){
        ll ret = 1;
        for(ll pri: primes){
            ll ve = get_v(pri, e);
            ll up = 1, dn = 1;
            for(int j = 0;j < pe.size();j++){
                ll up_T = min(ve, get_v(pri, phi_pe[j]));
                ll dn_T = min(ve - 1, get_v(pri, phi_pe[j]));
                if(dn_T < 0) dn = 0;
                if(i == j){
                    up = (__int128) up * h(pri, fac_N[i].first, fac_N[i].second, up_T) % pe[i];
                    if(dn_T >= 0) dn = (__int128) dn * h(pri, fac_N[i].first, fac_N[i].second, dn_T) % pe[i];
                }
                else{
                    up = (__int128) up * fpow(pri, up_T, pe[i]) % pe[i];
                    if(dn_T >= 0) dn = (__int128) dn * fpow(pri, dn_T, pe[i]) % pe[i];
                }
            }
            ret = (__int128) ret * (((up - dn) % pe[i] + pe[i]) % pe[i]) % pe[i];
        }
        a.push_back(ret);
    }
    return CRT(a, N);
}
 
ll solve4(ll e, ll N){
    ll pow2_e = get_v(2, e);
    ll pow2_N = get_v(2, N);
    
    ll e_n2 = e;
    while(e_n2 % 2 == 0) e_n2 /= 2;
    ll N_n2 = N;
    while(N_n2 % 2 == 0) N_n2 /= 2;
    ll two_r = N / N_n2; //2^r
    
    if(two_r <= 4) return g4(e, N);
    vector<ll> a;
    ll first;
    if(pow2_e == 1){
        first = - g_n2(e_n2, N_n2) % two_r;
    }
    else{
        if(pow2_e == 0) first = g_n2(e, N_n2) % two_r;
        else first = 0;
    }
    a.push_back(first);
    
    ll add = 0;
    if(1 <= min(pow2_e - 1, pow2_N - 2)) add = 1;
    ll ret = (__int128) g4_n2(e, N_n2) * (fpow(2, min(pow2_e - 1, pow2_N - 2) + 1, N_n2) - 1 + add) % N_n2;
    ll ret2 = 0, tmp = 1;
    for(int i = 0;i <= pow2_e && pow2_e <= pow2_N - 2;i++){
        ret2 = (ret2 + g4_n2(tmp * e_n2, N_n2)) % N_n2;
        tmp *= 2;
    }
    ll add2 = 0;
    if(pow2_e == 1) add2 = 1;
    ret2 = (__int128) ret2 * (fpow(2, pow2_e, 0) + add2) % N_n2;
    a.push_back((ret + ret2) % N_n2);
    
    ll part1 = (__int128) a[0] * N_n2 % (__int128) N * fpow(N_n2, two_r / 4 - 1, N) % N;
    ll part2 = (__int128) a[1] * two_r % (__int128) N * fpow(two_r, phi_N_n2 - 1, N) % N;
    return ((part1 + part2) % N + N) % N;
}
 
 
void init(ll N){
    factorize(fac_N, N);
    for(int i = 0;i < fac_N.size();i++){
        ll tmp = fpow(fac_N[i].first, fac_N[i].second - 1, 0) * (fac_N[i].first - 1);
        phi_N *= tmp;
        phi_pe.push_back(tmp);
        pe.push_back(fpow(fac_N[i].first, fac_N[i].second, 0));
        vector<pair<ll, ll> > fc_phi_pe;
        factorize(fc_phi_pe, phi_pe[i]);
        fac_ppe.push_back(fc_phi_pe);
    }
    for(int i = 0;i < fac_N.size();i++){
        prim_pe.push_back(find_prim(i));
    }
}
 
void init_n2(ll N){ //erase 2
    while(N % 2 == 0) N /= 2;
    factorize(fac_N_n2, N);
    for(int i = 0;i < fac_N_n2.size();i++){
        ll tmp = fpow(fac_N_n2[i].first, fac_N_n2[i].second - 1, 0) * (fac_N_n2[i].first - 1);
        phi_N_n2 *= tmp;
        phi_pe_n2.push_back(tmp);
        pe_n2.push_back(fpow(fac_N_n2[i].first, fac_N_n2[i].second, 0));
        vector<pair<ll, ll> > fc_phi_pe;
        factorize(fc_phi_pe, phi_pe_n2[i]);
        fac_ppe_n2.push_back(fc_phi_pe);
    }
}
 
void validator4(ll e, ll N){
    ll su = 0;
    ll lim = 5;
    printf("ex: ");
    for(ll i = 1;i < N;i++){
        ll ret = solve1(i, N);
        if(ret == e){
            su = (su + i) % N;
            if(lim) printf("%lld ", i,lim--);
        }
    }
    printf("validator: %lld\n", su);
}
 
void validator3(ll e, ll N){
    ll su = 0;
    ll lim = 5;
    printf("ex: ");
    for(ll i = 1;i < N;i++){
        ll ret = solve1(i, N);
        if(ret == e){
            su++;
            if(lim) printf("%lld ", i,lim--);
        }
    }
    printf("validator: %lld\n", su);
}
 
void validator2(ll a, ll ans, ll N){
    printf("validator: %lld\n", solve1(ans, N));
}
 
void validator1(ll a, ll N){
    ll su = 1, i;
    for(i = 1;i <= N;i++){
        su = su * a % N;
        if(su == 1) break;
    }
    if(i > N) i = 0;
    printf("validator: %lld\n", i);
}
 
int main(){
    ll N, Q;
    scanf("%lld %lld", &N, &Q);
    init(N);
    init_n2(N);
    while(Q--){
        ll t, a;
        scanf("%lld %lld", &t, &a);
        if(t == 1){
            ll ans = solve1(a, N);
            printf("%lld\n", ans);
    //        validator1(a, N);
        }
        if(t == 2){
            ll ans = solve2(a, N);
            printf("%lld\n", ans);
  //          validator2(a, ans, N);
        }
        if(t == 3){
            ll ans = solve3(a, N);
            printf("%lld\n", ans);
    //        validator3(a, N);
        }
        if(t == 4){
            ll ans = solve4(a, N);
            printf("%lld\n", ans);
    //        validator4(a, N);
        }
    }
}

# 코드 닫기