#include <cstdio>
using namespace std;
long long quickpow(long long m,long long n){
	long long res=1;
	while(n){
		if(n&1)
			res*=m;
		m*=m;
		n>>=1;
	}
	return res;
}
long long ans(long long n,long long m){
	long long f=quickpow(m,n);
	long long x=m;
	for(long long i=2;i*i<=x;i++){
		if(m%i==0){
			long long q=quickpow(i,n);
			f=f/q*(q-1);
			while(m%i==0)
				m/=i;
		}
	}
	if(m>1)
		f=f/quickpow(m,n)*(quickpow(m,n)-1);
	return f;
}
int main(){
	long long n,m;
	while(scanf("%I64d%I64d",&n,&m)!=EOF)
		printf("%I64d\n",ans(n,m));
	return 0;
}

• 今天携程的原题。 (649) yygy 2014-04-10 20:23:16