题解

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
long long qpower(long long a,int b)
{
	long long ans=1;
	for(;b;b>>=1,a*=a)if(b&1)ans=ans*a;
	return ans;
}
int main()
{
	scanf("%d%d",&m,&n);int fac=n;
	long long ans=1;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			ans*=qpower(i,m)-1;fac/=i;
			while(n%i==0)n/=i;
		}
	}
	if(n!=1)ans*=qpower(n,m)-1,fac/=n;
	ans=ans*qpower(fac,m);
	cout<<ans<<endl;
    return 0;
}