bzoj2440:[中山市选2011]完全平方数

Pre

第一次提交的时候(WA)了。

百思(死)不得其解(求根公式:我还活着呢!)。

最后发现交错题了(尴尬)。

不过这题转换到莫比乌斯函数有一点神奇巧妙。

还有一些小细节需要注意。

Solution

题目要求的就是(mu (i) e 0)的数。

二分+容斥原理。

注意计算的时候的细节。

特别是二分的时候，如果(r=l+1)，这时的(mid=l)，算出来有可能(r=mid)，这样(r=l-1)了。

而解决办法是不要直接

if (res == n) {
    l = r = mid;
    break;
}

这时可以缩小范围，继续找。

Code

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define xx first
#define yy second

using namespace std;

const int N = 1000000 + 5, M = 1000000;
int mu[N];
int pri[N], tot;
bool vis[N];

inline void init ();
inline ll cal (ll u) {
	ll res = 0;
    /*
    插一句，这里开始的时候我是初始化为
    ll res = u;
    但是发现错了，最后明白题解上面的不加这一句的原因，就是下面的i=1时的情况已经把这一种情况统计进去了，所以不用初始化统计。
    */
	for (ll i = 1; i * i <= u; ++i) {
		res += 1LL * mu[i] * (u / (i * i));
	}
	return res;
}

int main () {
	init ();
	int t;
	scanf ("%d", &t);
	while (t--) {
		ll n;
		scanf ("%lld", &n);
		ll l = 1, r = INT_MAX * 10LL, mid;
		while (l < r) {
			mid = (l + r) / 2;
			ll res = cal (mid);
			if (res == n) {
				l = r = mid;
				break;
			}
			else if (res < n) {
				l = mid + 1;
			}
			else if (res > n){
				r = mid - 1;
			}
		}
		while (cal (r) == cal (r - 1)) {
			--r;
		}//插一句，有一些巨佬的二分可以不用这一句，但是我只有加了才能A(本地测出来的)
		printf ("%lld
", r);
	}
	return 0;
}

inline void init () {
	mu[1] = 1;
	for (int i = 2; i <= M; ++i) {
		if (!vis[i]) {
			pri[++tot] = i;
			vis[i] = 1;
			mu[i] = -1;
		}
		for (int j = 1; j <= tot; ++j) {
			if (pri[j] * i >= M) {
				break;
			}
			vis[pri[j] * i] = 1;
			if (i % pri[j] == 0) {
				mu[pri[j] * i] = 0;
				break;
			}
			else {
				mu[pri[j] * i] = -mu[i];
			}
		}
	}
}

贴上大佬的代码。

出处:ljh2000的题解

inline bool check(LL x){
    LL div=sqrt(x); int tot=0;
    for(int i=1;i<=div;i++) {
    tot+=mobius[i] * (x/(i*i));
    }
    //tot=x-tot;
    if(tot>=k) return true;
    return false;
}
inline void work(){
    init(); int T=getint(); LL mid;
    while(T--) {
    k=getint(); l=1; r=inf; ans=inf;
    while(l<=r) {
        mid=(l+r)/2;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d
",ans);
    }
}

Conclusion

莫比乌斯相关的真的很生疏，玄学啊。