#P18632. Elliptic Curve Problem

Elliptic Curve Problem

Elliptic Curve Problem

这个问题在一些国家也许已经广为人知,但如果从来没有人把它作为题目提出,其他国家的人又如何了解它呢?

给定奇素数 pp,求闭区间 [l,r][l,r] 内有多少个数是模 pp 的二次剩余。

按照本题的定义,xx 是模 pp 的二次剩余,当且仅当

x(p−1)/2≡1(modp).x^{(p-1)/2}\equiv 1\pmod p.

输入格式

一行三个整数 p,l,rp,l,r。保证 pp 是奇素数。

输出格式

输出一个整数,表示所求数量。

数据范围

3≤p≤10113\le p\le10^{11},1≤l≤r<p1\le l\le r<p。

样例输入 1

11 3 8

样例输出 1

3

样例输入 2

998244353 11451400 919810000

样例输出 2

454174074

样例输入 3

96311898227 25437319919 55129361817

样例输出 3

14846091352