正题

题目链接:https://www.luogu.com.cn/problem/P2231

---

题目大意

求一个由$[1,m]$的整数组成的长度为$n$的序列使得他们的$gcd$和$m$互质。

---

解题思路

考虑容斥减去不合法的答案。那就是要求序列的$gcd$和$m$不互质的个数，那么我们依旧需要容斥计算这个问题，显然一个约数$x$的贡献就是$(\frac{m}{x}{)}^n$，设$f_i$表示第$i$个约数的容斥系数为$-{\sum }_{d_j|d_i}{f}_i$。

这样理论时间复杂度就是约数个数的平方，加上快速幂，也就是接近于$O({\sqrt{m}}^2\log n)$。然而时间复杂度很小。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; ll n,m,q[1100000],cnt,ans,f[1100000]; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x;x=x*x;b>>=1;}return ans; } int main() {scanf("%lld%lld",&n,&m);for(ll i=2;i*i<=m;i++){if(m%i==0){q[++cnt]=i;if(i*i!=m)q[++cnt]=m/i;}}q[++cnt]=m; sort(q+1,q+1+cnt);for(ll i=1;i<=cnt;i++){f[i]=1;for(ll j=1;j<i;j++)if(q[i]%q[j]==0)f[i]-=f[j];ans+=power(m/q[i],n)*f[i];}printf("%lld",power(m,n)-ans); }

总结

以上是生活随笔为你收集整理的P2231-[HNOI2002]跳蚤【容斥】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。