正題

題目鏈接:
https://www.luogu.org/problem/P4318
https://www.lydsy.com/JudgeOnline/problem.php?id=2440

---

題目大意

完全平方數(shù)只對應(yīng)任意一個的正整數(shù)滿足$d\mid n,d^2?n$(也就是$n$的質(zhì)因數(shù)分解后都沒有次數(shù))。
求第$k$個完全平方數(shù)

---

解題思路

考慮二分答案，將問題轉(zhuǎn)換為判定求$1～mid$內(nèi)有多少個完全平方數(shù)。
考慮容斥，我們考慮用$1～\sqrt{m}id$這些數(shù)中的無平方因子數(shù)進行容斥。而因為會有重復(fù)，我們發(fā)現(xiàn)對應(yīng)$x$來說的容斥系數(shù)就是$\mu (x)$(首先保證了一定是無平方因子數(shù)，然后若只有一個質(zhì)因數(shù)$\mu (x)=?1$否則$\mu (x)=1$這樣就是容斥系數(shù)了)。而對應(yīng)$x$來說可以組成$?\frac{n}{x^2}?$個平方因子數(shù)，所以個數(shù)為
$$\sum _{i=1}^{\sqrt{m}}\mu (x)?\frac{mid}{i^2}?$$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=100010; ll T,n,l,r,mu[N+10],prime[N+10],cnt; bool v[N+10]; ll check(ll n) {ll ans=0;for(ll i=1;i*i<=n;i++)ans+=mu[i]*(n/(i*i));return ans; } int main() {scanf("%lld",&T);mu[1]=1;for(ll i=2;i<=N;i++){if(!v[i])mu[i]=-1,prime[++cnt]=i;for(ll j=1;j<=cnt&&i*prime[j]<=N;j++){v[i*prime[j]]=1;if(!(i%prime[j])) break;mu[i*prime[j]]=-mu[i];}}while(T--){scanf("%lld",&n);l=1;r=2*n;while(l<=r){ll mid=(l+r)/2;if(check(mid)>=n) r=mid-1;else l=mid+1;}printf("%lld\n",l);} }

總結(jié)

以上是生活随笔為你收集整理的P4318,bzoj2440-完全平方数【二分答案,莫比乌斯函数,容斥】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。