完全平方數

HYSBZ - 2440

小 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

思路：

首先我們可以在外層套一個二分，把問題轉化為判斷問題，

即只需要能判斷給定一個正整數X，在1~X之間，是否存在mid個數是他喜歡的數。

根據容斥原理，答案就是：0個質數乘積的平方的倍數的數量（1的倍數）- 1個質數乘積的平方的倍數的數量（4,9,25的倍數）+ 2個質數乘積的平方的倍數的數量（36,100的倍數）-3個質數乘積...+ 4個 。。。。。

即加上偶數個質數乘積的平方的倍數個數，減去奇數個質數乘積的平方的倍數個數。

來看下莫比烏斯(M?bius)函數：

對于每個正整數n(n ≥ 2)，設它的質因數分解式為：

　　

　　根據這個式子定義n的莫比烏斯函數為：

　　

給定一個整數X，求在1~X之間，是否存在mid個數是他喜歡的數。

我們可以這樣求：

枚舉數i在1~sqrt（X）之間

那么i對這個答案的貢獻就是 mu[i] * (X/ (i * i))

(X/ (i * i)) 是 在1~X中，有多少個數是i的平方的倍數。

而他對答案是加還是減，即系數就恰好是u（i），u（）是莫比烏斯函數。

外層正常的套路二分即可。

又因為莫比烏斯函數是一個積性函數，所以可以直接線篩出來。

不會的話可以百度搜幾篇關于莫比烏斯函數和對應的線篩寫法即可。

細節見代碼

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl #define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c)) #define du2(a,b) scanf("%d %d",&(a),&(b)) #define du1(a) scanf("%d",&(a)); using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;} void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}} void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}inline void getInt(int *p); const int N = 1000010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ bool vis[N]; long long prim[N], mu[N], sum[N], cnt; void get_mu(long long n) {mu[1] = 1;for (long long i = 2; i <= n; i++) {if (!vis[i]) {mu[i] = -1; prim[++cnt] = i;}for (long long j = 1; j <= cnt && i * prim[j] <= n; j++) {vis[i * prim[j]] = 1;if (i % prim[j] == 0) { break; }else { mu[i * prim[j]] = -mu[i]; }}}for (long long i = 1; i <= n; i++) { sum[i] = sum[i - 1] + mu[i]; } } ll getnum(ll mid) {ll q = (sqrt(mid) + eps);ll res = 0ll;for (ll i = 1ll; i <= q; ++i) {res += mu[i] * (mid / (i * i));}return res; } ll solve(ll x) {ll l = 1ll;ll r = x << 1;ll mid;ll ans;while (l <= r) {mid = (l + r) >> 1;if (getnum(mid) < x) {l = mid + 1ll;} else {r = mid - 1ll;ans = mid;}}return ans; } int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);get_mu(N - 1);int t;du1(t);while (t--) {ll n;scanf("%lld", &n);printf("%lld\n", solve(n) );// solve(n)}return 0; }inline void getInt(int *p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}} else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉載于:https://www.cnblogs.com/qieqiemin/p/11537681.html

總結

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

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