考虑方程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;
}
/**/