费马大定理（原根+扩欧）
考虑方程x^k+y^k=z^k，其中x,y,z,k≠0 ，且均为正整数。众所周知，由费马大定理，当k> 2时，方程无解。现在考虑在模意义下的问题。
给定一个质数P，以及一个正整数L，现在想知道有多少个整数k，满足1<=k<=L，存在x,y,z，0<x,y,z<P，使得x^k+y^k≡z^k (mod P)
输入
输入两个整数P,L。
输出
输出一个整数代表合法的k的个数
样例输入 Copy
3 10
样例输出 Copy
5
考虑用P的原根root表示
即
我们考虑找出满足下面条件的(t1, t2)对
那么求解上面方程组的条件就是
考虑对于扩欧不定方程（裴蜀定理）时的条件，需要满足(k, p - 1) | t1 以及 (k, p - 1) | t2
所以需满足(k, p - 1) | (t1, t2)
然后直接枚举即可
/**/
#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
LL n;
int p, tot, cnt;
int prim[78505], fa[205], a[1000005];
bool vis[1000005], b[1000005];
void get(){
vis[1] = vis[0] = 1;
for (int i = 2; i <= 1000000; i++){
if(!vis[i]) prim[tot++] = i;
for (int j = 0; j < tot && prim[j] * i <= 1000000; j++){
int x = prim[j] * i;
vis[x] = true;
if(i % prim[j] == 0) break;
}
}
}
LL poww(LL x, LL num, LL mod){
LL res = 1;
while(num){
if(num & 1) res = res * x % mod;
x = x * x % mod;
num >>= 1;
}
return res;
}
int get_rt(int x){
int t = x - 1;
// get();
// printf("%d\n", tot);
for (int i = 2; i * i <= t; i++){
if(t % i == 0){
fa[cnt++] = i;
while(t % i == 0) t /= i;
}
}
if(t > 1) fa[cnt++] = t;
int f = 0;
for (int i = 2; i < x; i++){
f = 0;
for (int j = 0; j < cnt; j++){
if(poww(i, (x - 1) / fa[j], x) == 1) {f = 1; break;}
}
if(!f) return i;
}
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d %lld", &p, &n);
int rt = get_rt(p);
LL leave = n % (p - 1), num = n / (p - 1);
LL mul = 1, ans = 0;
for (int i = 1; i < p; i++) mul = mul * rt % p, a[mul] = i;
for (int i = 2; i < p; i++) b[__gcd(a[i], a[i - 1])] = 1;
for (int i = 1; i < p; i++) printf("%d ", a[i]);
printf("\n");
for (int i = 1; i < p; i++){
for (int j = i << 1; j < p && !b[i]; j += i) b[i] |= b[j];
}
for (int i = 1; i < p; i++) if(b[__gcd(i, p - 1)]) ans += num + (i <= leave);
printf("%lld\n", ans);
return 0;
}
/**/
