描述

小 X 自幼就很喜歡數。但奇怪的是，他十分討厭完全平方數。他覺得這些數看起來很令人難受。由此，他也討厭所有是完全平方數的正整數倍的數。然而這絲毫不影響他對其他數的熱愛。這天是小X的生日，小 W 想送一個數給他作為生日禮物。當然他不能送一個小X討厭的數。他列出了所有小X不討厭的數，然后選取了第 K個數送給了小X。小X很開心地收下了。然而現在小 W 卻記不起送給小X的是哪個數了。你能幫他一下嗎？

分析

• 本來準備做數表, 抱著學習的心態看了看莫比烏斯反演, 看到莫比烏斯函數之后不想再往下看了就來做了這個題.
• 這是一種基于二分的方法. 用到了容斥原理和莫比烏斯函數
• 根據容斥原理可知 對于sqrt(x)以內所有的質數 有
• ? x以內的無平方因子數
• = 0個質數乘積的平方的倍數的數的數量(1的倍數) = x
• - 每個質數的平方的倍數的數的數量(9的倍數,25的倍數,...)
• +每2個質數乘積的平方的倍數的數的數量(36的倍數,100的倍數,...)
• ...
• 容易發現每個乘積a前面的符號恰好是mu[a].?x以內i^2的倍數有X/(i^2)向下取整. 所以二分, 計算x以內的無平方因子數. 直到找到第k個無平方因子數.

代碼

#include #include using namespace std; typedef long long int lli;const int maxn = 100000 + 10; int c, prime[maxn], mu[maxn]; bool vis[maxn];void get_mu() {mu[1] = 1;for(int i = 2; i < maxn; i++) {if(!vis[i]) prime[++c] = i, mu[i] = -1;for(int j = 1; prime[j]*i < maxn; j++) {int k = prime[j] * i;vis[k] = 1;if(i % prime[j] == 0) { mu[k] = 0; break; }mu[k] = -mu[i];}} }lli calc(int x) {lli ret = 0;int m = (int)(sqrt(x) + 0.5);for(int i = 1; i <= m; i++) ret += (lli)mu[i] * x/(i*i);return ret; }lli twiDivide(lli n) {lli l = n, r = n << 1;while(l <= r) {lli m = (l+r) >> 1;if(calc(m) >= n) r = m-1; else l = m+1;}return r+1; }int main() {get_mu();int T;scanf("%d", &T);while(T--) {lli n;scanf("%lld", &n);printf("%lld\n", twiDivide(n));}return 0; }

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的BZOJ-2440-完全平方数-中山市选2011-容斥原理-莫比乌斯函数-二分查找的全部內容，希望文章能夠幫你解決所遇到的問題。

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