题意：题意和POJ3090 类似只是变成三维，可以简化为求gcd(a,b,c)=1方案数, 0<= a,b,c <=n, n <= 1e6
思路：
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int maxn = 1e6+5; bool vis[maxn]; int mu[maxn], prime[maxn]; void init() { memset(vis, 0, sizeof(vis)); mu[1] = 1; int cnt = 0; for(int i = 2; i < maxn; i++) { if(!vis[i]) { prime[cnt++] = i; mu[i] = -1; } for(int j = 0; j < cnt && i*prime[j] < maxn; j++) { vis[i*prime[j]] = 1; if(i%prime[j]) mu[i*prime[j]] = -mu[i]; else { mu[i*prime[j]] = 0; break; } } } } int main(void) { int t; init(); cin >> t; while(t--) { ll n; scanf("%lld", &n); ll ans = 3; for(int i = 1; i <= n; i++) ans += mu[i]*(n/i)*(n/i)*(n/i+3); printf("%lld\n", ans); } return 0; }
