#P13771. 费马大定理

    ID: 12979 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-原根快速幂试除法分解质因数约数成对枚举固定一个变量消去另一维莫比乌斯反演时间戳避免清空数组

费马大定理

题目描述

考虑方程 xk+yk=zkx^k + y^k = z^k,其中 x,y,z,kx,y,z,k 均为正整数。众所周知,由费马大定理,当 k>2k>2 时方程无解。现在考虑在模意义下的问题。

给定一个质数 PP,以及一个正整数 LL,现在想知道有多少个整数 kk,满足 1≤k≤L1 \le k \le L,存在 x,y,zx,y,z,0<x,y,z<P0 < x,y,z < P,使得:

xk+yk≡zk(modP).x^k + y^k \equiv z^k \pmod P.

输入格式

输入两个整数 P, L。

输出格式

输出一个整数,代表合法的 k 的个数。

数据范围

  • 对于 10% 的数据:P <= 100, L <= 100
  • 对于 30% 的数据:P <= 5000, L <= 5000
  • 对于 60% 的数据:P <= 1e6, L <= 1e5
  • 对于 100% 的数据:P <= 1e6, L <= 1e18

输入样例

样例输入 1

3 10

样例输入 2

233 1000

样例输入 3

692707 470472961806427201

输出样例

样例输出 1

5

样例输出 2

966

样例输出 3

470453944730018769