51nod 1662 構造模函數

題目

看了代碼就知道怎麼做了。。。

#include<bits/stdc++.h>
using namespace std;
const int M=1e9+7;
int k,p,s,m;
int pw(int x,int y){
	int z=1;
	for (;y;y>>=1,x=1ll*x*x%M)
		if (y&1) z=1ll*z*x%M;
	return z;
}
int main(){
	scanf("%d%d",&p,&k);
	if (k<2) printf("%d",pw(p,p-1+k));
	else{
		for (s=k;s!=1;s=1ll*s*k%p,m++);
		printf("%d",pw(p,(p-1)/(m+1)));
	}
}