SP7001 VLATTICE

作者:

在

,

$$ \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;
}

 

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。