題目鏈接

Description

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

Input

包含多組測試數據。文件第一行有一個整數 T，表示測試
數據的組數。
第2 至第T+1 行每行有一個整數Ki，描述一組數據，含義如題目中所描述。

Output

含T 行，分別對每組數據作出回答。第 i 行輸出相應的
第Ki 個不是完全平方數的正整數倍的數。

Sample Input

4 1 13 100 1234567

Sample Output

1 19 163 2030745

HINT

對于 100%的數據有 1 ≤ Ki ≤ 10^9，T ≤ 50

思路

• 不喜歡完全平方數及其整數倍，符合要求的數字拆分成質因數的冪次為1
• 查詢的范圍大，二分枚舉答案
• 對于區間[1, X]中的數我們可以把不符合條件的數刪除，剩下的數就是符合條件的數。我們刪掉所有$i^2$的倍數，但是這樣可能會有重復比如刪除所有$2^2，3^2$的倍數中$6^2$被重復刪掉了。這里就要用上容斥原理。我們發現符合莫比烏斯函數的性質：奇數個質因子系數為-1，偶數為+1，其余為零

#include <iostream> #include <stdio.h> #include <map> #include <vector> #include <set> #include <queue> #include <stack> #include <cstring> #include <cmath> #include <algorithm> #define lowbit(x) (x & (-x)) #define mem(a, b) memset(a, b, sizeof(a)) #define rep(i, a, n) for (int i = a; i < n; ++i) #define mid ((l + r)>>1) #define lc rt<<1 #define rc rt<<1|1 typedef long long LL; #define maxn 100005using namespace std;int mo[maxn], vis[maxn], prime[maxn];void init () {mo[1] = 1;mem(vis, 0);int len = 0;for (int i = 2; i < maxn; ++i) {if (!vis[i]) {prime[len++] = i;mo[i] = -1;}for (int j = 0; j < len && (LL)prime[j] * i < maxn; ++j) {vis[ i * prime[j] ] = 1;if (i % prime[j] == 0) {mo[ i * prime[j] ] = 0;break;}mo[ i * prime[j] ] = -mo[i];}} } int solve(int x) {int sum = 0;for (LL i = 1; i <= sqrt(x); ++i) {sum += mo[i] * (x / (i*i));}return sum; }int main() { #ifndef ONLINE_JUDGE// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout); #endifinit();int T;scanf("%d", &T);while (T--) {int n;scanf("%d", &n);LL l = 1, r = 2e9;while (l < r) {if (solve(mid) >= n) r = mid;else l = mid + 1;}printf("%d\n", l);}return 0; }

總結

以上是生活随笔為你收集整理的BZOJ-2440 (莫比乌斯函数)的全部內容，希望文章能夠幫你解決所遇到的問題。

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