AcWing 2098. 跳蚤
原题链接
困难
作者:
安之mx
,
2024-01-28 11:43:59
,
所有人可见
,
阅读 26
C++ 代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
int n,m;
int factor[10000],cnt;
int pr[10000];
ll quickpow(ll a,ll n)
{
ll res = 1;
while (n)
{
if (n&1) res = res*a;
a = a *a;
n >>= 1;
}
return res;
}
void factorfind(int x)
{
cnt = 0;
for (int i = 2 ; i * i <= x ; i ++)
{
if (x%i==0)
{
factor[++cnt] = i;
while (x%i==0)
x /= i;
}
}
if (x!=1)
factor[++cnt] = x;
return;
}
ll dfs(int now,int all,int pos)
{
if (now==all)
{
int x = m;
for (int i = 1; i <= all ; i ++)
x /= pr[i];
return quickpow(x,n);
}
ll res = 0;
for (int i = pos ; i <= cnt; i ++)
{
pr[now+1] = factor[i];
res += dfs(now+1,all,i+1);
}
return res;
}
ll solve(int t)
{
return dfs(0,t,1);
}
int main(){
while (~scanf("%d%d",&n,&m))
{
factorfind(m);
ll ans = 0;
for (int i = 1 ; i <= cnt ; i ++)
{
ll temp = solve(i);
if (i&1) ans += temp;
else ans -= temp;
}
ans = quickpow(m,n)-ans;
printf("%lld\n",ans);
}
return 0;
}