【NOIP2017提高A组模拟9.5】心灵治愈

【NOIP2017提高A组模拟9.5】心灵治愈

Description

Input

Output

Sample Input

输入1：
2 3

输入2：
8 8

Sample Output

输出1：
8

输出2：
16711680

Data Constraint

Hint

题解

code

#include<cstdio>
#include<cstdlib>
#define ll long long
#define R register
using namespace std;
const ll mo=1e9+7;
ll n,m,k,pr[50],cnt=0,ans;
inline ll power(ll x,ll y){ll re=1;while(y){if(y&1)re=re*x%mo;y>>=1,x=x*x%mo;}return re;
}
int main(){scanf("%lld%lld",&n,&m);k=m,ans=power(m%mo,n);for(R ll i=2;i*i<=k;++i)if(k%i==0){pr[++cnt]=i;while(k%i==0)k/=i;}if(k>1)pr[++cnt]=k;for(R int i=1;i<(1<<cnt);++i){//枚举可能情况ll tot=0,tmp=1;for(R int j=1;j<=cnt;++j)if(i&(1ll<<(j-1)))++tot,tmp*=pr[j];if(tot&1)ans=(ans-power((m/tmp)%mo,n)+mo)%mo;//容斥计算方案数else ans=(ans+power((m/tmp)%mo,n))%mo;}printf("%lld",ans);
}