正題

題目鏈接: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]跳蚤【容斥】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。