https://www.luogu.org/problemnew/show/P2231
题意相当于：
有n个位置a[1..n]，每个位置可以填[1,m]中任一个整数，问共有多少种填法满足gcd(a[1],a[2],..,a[n],m)=1
可以反演一下
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const ll N=;
ll prime[N+],len;
bool nprime[N+];
ll ans;
ll poww(ll a,ll b)
{
ll bs=a,an=;
for(;b;b>>=,bs*=bs)
if(b&)
an*=bs;
return an;
}
ll getmu(ll x)
{
ll i,ans=,ed=sqrt(x+0.5);
bool fl;
for(i=;i<=len&&prime[i]<=ed;i++)
{
fl=;
while(x%prime[i]==)
{
if(fl) return ;
fl=;
x/=prime[i];
ans*=(-);
}
}
if(x!=) ans*=(-);
return ans;
}
ll n,m;
void work(ll d)
{
ans+=poww(m/d,n)*getmu(d);
}
int main()
{
ll i,j;
for(i=;i<=N;i++)
{
if(!nprime[i]) prime[++len]=i;
for(j=;j<=len&&i*prime[j]<=N;j++)
{
nprime[i*prime[j]]=;
if(i%prime[j]==) break;
}
}
scanf("%lld%lld",&n,&m);
ll ed=sqrt(m+0.5);
for(i=;i<=ed;i++)
if(m%i==)
{
work(i);
if(m/i!=i) work(m/i);
}
printf("%lld",ans);
return ;
}