QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 5021. 六元不定方程

Statistics

给定整数 $N,r$,求有多少六元有序数组 $(a,b,c,a',b',c')$ 满足同余方程 $ab+a'b'\equiv bc+b'c'\equiv ca+c'a'\equiv r\pmod N$。其中 $a,b,c,a',b',c'\in\{0,1,\cdots,N-1\}$。

保证 $\mu(N) \ne 0$,即 $N$ 所有素因数的次数都为 $1$。

输入格式

两个整数 $N,r$。

输出格式

一个整数,表示答案。答案对 $998\,244\,353$ 取模。

样例数据

样例 1 输入

2 0

样例 1 输出

20

样例 2 输入

15 1

样例 2 输出

3472

子任务

对于所有数据,保证 $0 \le r < N \le 10^{18}$,$N \ge 2$,$\mu(N) \ne 0$。

子任务编号 分值 $N \leq$ 特殊限制
$1$ $7$ $50$
$2$ $8$ $500$
$3$ $15$ $10^7$
$4$ $20$ $10^{10}$ $r=0$
$5$ $20$ $r=1$
$6$ $10$ $10^{18}$ $N$ 为素数
$7$ $20$