#1658. 六元不定方程

    ID: 1658 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1033来源:qoj.ac数据:公开样例数学分治数论

六元不定方程

六元不定方程

题目描述

标题: 六元不定方程 - 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 无

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 0
20

样例 2

15 1
3472