$$ \text{因为题目中要求}a,b,c\text{都可以取到0,所以我们先考虑}abc\text{都不为0的情况} \\ \sum_{1\le i\le n}{\sum_{1\le j\le n}{\sum_{1\le k\le n}{\left[ gcd\left( i,j,k \right) \ =\ 1 \right]}}} \\ \sum_{1\le i\le n}{\sum_{1\le j\le n}{\sum_{1\le k\le n}{\sum_{d|gcd\left( i,j,k \right)}{\mu \left( d \right)}}}} \\ \sum_{1\le d\le n}{\mu \left( d \right) \sum_{1\le i\le n}{\sum_{1\le j\le n}{\sum_{1\le k\le n}{\sum_{d|gcd\left( i,j,k \right)}{\left[ d|gcd\left( i,j,k \right) \right]}}}}} \\ \sum_{1\le d\le n}{\mu \left( d \right) \sum_{1\le i\le \lfloor \frac{n}{d} \rfloor}{\sum_{1\le j\le \lfloor \frac{n}{d} \rfloor}{\sum_{1\le k\le \lfloor \frac{n}{d} \rfloor}{1}}}} \\ =\sum_{1\le d\le n}{\mu \left( d \right) \lfloor \frac{n}{d} \rfloor ^3} \\ \text{再考虑}abc\text{只有一个为0的情况,这时候等价于二维平面上} \\ 3\sum_{1\le d\le n}{\mu \left( d \right) \lfloor \frac{n}{d} \rfloor ^2} \\ \text{因为}abc\text{一个为0有三种情况,所以需要乘}3 \\ \text{在考虑}abc\text{有两个为0的情况} \\ \text{这时候是一条直线,只有一种可能} \\ \text{所以最后答案为} \\ 3+\sum_{1\le d\le n}{\mu \left( d \right) \lfloor \frac{n}{d} \rfloor ^2\left( \lfloor \frac{n}{d} \rfloor +3 \right)} $$
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <inttypes.h>
#define debug(x) std::cout << #x << " = " << x << std::endl;
typedef long long int int_t;
using std::cin;
using std::endl;
using std::cout;
const int_t LARGE = 1000000;
int_t factor[LARGE + 1];
bool isPrime[LARGE + 1];
int_t mu[LARGE + 1];
void init() {
std::fill(isPrime + 1,isPrime + 1 + LARGE,true);
isPrime[1] = false;
for(int_t i = 2; i <= LARGE ; i++) {
if(isPrime[i]) {
for(int_t j = i * i; j <= LARGE ; j += i) {
factor[j] = i;
isPrime[j] = false;
}
factor[i] = i;
mu[i] = -1;
}
}
mu[1] = 1;
for(int_t i = 2; i <= LARGE ; i ++) {
if(isPrime[i] == false) {
int_t factor = ::factor[i];
if((i / factor) % factor == 0) mu[i] = 0;
else mu[i] = mu[i / factor] * mu[factor];
}
}
for(int_t i = 2; i <= LARGE ; i ++) {
mu[i] += mu[i - 1];
}
}
int main() {
init();
int T;
scanf("%d",&T);
for(int_t _i = 1; _i <= T; _i ++) {
int_t x;
scanf("%lld",&x);
int_t result = 3;
int_t i = 1;
while(i <= x) {
int_t next = x / (x / i);
int_t c = x / i;
result += (mu[next] - mu[i - 1]) * (c * c * (c + 3));
i = next + 1;
}
printf("%lld\n",result);
}
return 0;
}
发表回复