SPOJ 7001 Visible Lattice Points（莫比乌斯反演）

本文主要是介绍SPOJ 7001 Visible Lattice Points（莫比乌斯反演），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

莫比乌斯反演，注意0的情况特殊考虑下就可以了

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 1000005;int mo[N], prime[N], pn;
bool vis[N];void Moblus() {memset(vis, false, sizeof(vis));mo[1] = 1; pn = 0;for(int i = 2; i < N; i++) {if(!vis[i]) {prime[pn++] = i;mo[i] = -1;}for(int j = 0; j < pn; j++) {if(i * prime[j] >= N) break;vis[i * prime[j]] = true;if(i % prime[j] == 0) {mo[i * prime[j]] = 0;break;} else mo[i * prime[j]] = -mo[i];}}
}typedef long long ll;int t, n;int main() {Moblus();scanf("%d", &t);while (t--) {scanf("%d", &n);ll ans = 3;for (int i = 1; i <= n; i++) {ans += (ll)mo[i] * (n / i) * (n / i) * (n / i);ans += (ll)mo[i] * (n / i) * (n / i) * 3;}printf("%lld\n", ans);}return 0;
}

这篇关于SPOJ 7001 Visible Lattice Points（莫比乌斯反演）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---