mobius/A.cpp at master · foreignbill/mobius · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>

using namespace std;
const int maxn = 1000005;
typedef long long ll;
int a,b,c,d,k;
bool p[maxn];
int prime[maxn],top;
int mu[maxn];
int summu[maxn];
template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}

template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);}
template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}
template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}
void init(){
	memset(p,0,sizeof p);
	memset(mu,0,sizeof mu);
	top=0;
	mu[1]=1;
	for(int i=2;i<maxn;i++){
		if(!p[i]){
			prime[++top]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=top && i*prime[j]<maxn;j++){
			p[i*prime[j]]=1;
			if(i % prime[j] == 0){
				break;
			}
			mu[i * prime[j]] = -mu[i];
		}
	}
	summu[0]=0;
	for(int i=1;i<maxn;i++)
		summu[i]=summu[i-1]+mu[i];
}

int main(){
	int T,n;
	init();
	read(T);
	for(;T--;){
		read(n);
		if(!n){
			puts("0");
			continue;
		}
		ll res=3;
		int la=0;
		for(int i=1;i<=n;i=la+1){
			la=n/(n/i);
			res += (ll)(summu[la]-summu[i-1])*(n/i)*(n/i)*(n/i+3);
		}
		printf("%lld\n",res);
	}
	return 0;
}