192 素域椭圆曲线数点

内存限制:512 MB 时间限制:2000 ms

题目描述

这是一道模板题。

给定质数 $p\ge 5$,$a,b\in\mathbb{F}_p$ 满足 $4a^3+27b^2\ne 0$。

求椭圆曲线 $y^2z=x^3+axz^2+bz^3$ 的点的个数。满足方程的一组不全为 $0$ 的 $(x,y,z)\in\mathbb{F}_p^3$ 称为椭圆曲线上的点,若 $\lambda\in\mathbb{F}_p$,$\lambda\ne 0$,那么 $(x,y,z)$ 和 $(\lambda x,\lambda y,\lambda z)$ 被考虑为同一个点。

输入格式

一行,三个整数 $p,a,b$,用空格分隔。

输出格式

一行,一个正整数表示答案。

样例 1

$6$ 个点分别为 $(0,1,0),(4,1,1),(4,6,1),(5,0,1),(6,1,1),(6,6,1)$。

样例 2

数据范围与提示

保证 $5\le p<2^{60}$,$0\le a,b<p$。

样例

样例输入 1

7 1 3

样例输出 1

6

样例输入 2

318743863128339547 105037157051741234 168782265549960835

样例输出 2

318743863620705102