#PQJ1033x5021. QOJ 1033_5021
QOJ 1033_5021
标题: 六元不定方程 - Problem - QOJ.ac
#5021. 六元不定方程
The problem was used in the following contests:
给定整数 N,r,求有多少六元有序数组 (a,b,c,a′,b′,c′) 满足同余方程 ab+a′b′≡bc+b′c′≡ca+c′a′≡r(modN)。其中 a,b,c,a′,b′,c′∈{0,1,⋯,N−1}。
保证 μ(N)≠0,即 N 所有素因数的次数都为 1。
输入格式
两个整数 N,r。
输出格式
一个整数,表示答案。答案对 998244353 取模。
样例数据
样例 1 输入
2 0
样例 1 输出
20
样例 2 输入
15 1
样例 2 输出
3472
子任务
对于所有数据,保证 0≤r<N≤1018,N≥2,μ(N)≠0。
子任务编号 分值 N≤ 特殊限制 1 7 50 无 2 8 500 3 15 107 4 20 1010 r=0 5 20 r=1 6 10 1018 N 为素数 7 20 无