#PQJ1033x5021. QOJ 1033_5021

    ID: 2532 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2022-2023 集训队互测数学枚举数论

QOJ 1033_5021

标题: 六元不定方程 - Problem - QOJ.ac

#5021. 六元不定方程

Statistics

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 无