摘要:蒟蒻 ( ext{brz}) 最近学习了莫比乌斯函数,由于学到了新东西蒟蒻 ( ext{brz}) 感觉很高兴,一旁的神牛 ( ext{lzy}) 十分不屑,随手丢了一道水题就难住了蒟蒻 ( ext{brz})...
对于原函数若 (i,j) 互质,则(mu(ij)=mu(i)mu(j)),否则(mu(ij)=0),于是有:
[sum_{i=1}^{n} sum_{j=1}^{n}{mu(ij)} quad = quad sum_{i=1}^{n} sum_{j=1}^{n}{mu(i)mu(j)} [gcd(i,j)=1]
]
[quadquadquadquadquadquad = quad sum_{i=1}^{n} sum_{j=1}^{n}{mu(i)mu(j)} sum_{d|gcd(i,j)}{mu(d)}
]
[quadquadquadquadquadquadquadquadquad = quad sum_{i=1}^{n} sum_{j=1}^{n}{mu(i)mu(j)} sum_{k=1}^{n}{mu(k)} [k|gcd(i,j)]
]
[quadquadquadquadquadquad = quad sum_{k=1}^{n}{mu(k)} sum_{i=1}^{lfloor frac{n}{k}
floor}{mu(ik)} sum_{j=1}^{lfloor frac{n}{k}
floor}{mu(jk)}
]
令(S(k,m) = sum_{i = 1}^{m}{mu(ik)}),代入得:(sum_{k=1}^{n} mu(k) S(k,lfloor frac{n}{k} floor)^{2}),得到下图(8 imes8)的矩阵:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
---|---|---|---|---|---|---|---|---|
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | 1 | 1 | 1 | 1 | ||||
3 | 1 | 1 | ||||||
4 | 1 | 1 | ||||||
5 | 1 | |||||||
6 | 1 | |||||||
7 | 1 | |||||||
8 | 1 |
图中值为1的位置为有效点,而在左上角(i imes i)内的有效点的值的累加和就是(n=i)时的原函数值。
S函数的值:(S(k,m) = S(k,m-1) + mu(mk))
有效点的值:(val(k,i) = mu(k)S(k,i)^{2} - mu(k)S(k,i-1)^{2})
原函数的值:(ans(n) = ans(n-1) + sum_{d|n}{val(d,n)})
时间复杂度(O(nln(n) + T))
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4+1;
int prime[maxn], tot, mu[maxn];
bool vis[maxn];
vector<int> g[maxn];
int s[maxn], ans[maxn];
void seive(int n) {
vis[1] = true, mu[1] = 1;
for(int i = 2; i <= n; ++ i) {
if (!vis[i]) prime[++tot] = i, mu[i] = -1;
for(int j = 1; 1ll * i * prime[j] <= n; ++ j) {
vis[i * prime[j]] = true;
if (i % prime[j] == 0) break;
mu[i*prime[j]] = mu[i] * mu[prime[j]];
}
}
}
int main() {
seive(maxn-1);
for(int i = 1; i <= maxn-1; ++ i) {
for(int j = i; j <= maxn-1; j += i) {
g[j].push_back(i);
}
}
for(int i = 1; i <= maxn-1; ++ i) {
ans[i] = ans[i-1];
for(auto j: g[i]) {
ans[i] -= mu[j] * s[j] * s[j];
s[j] += mu[i];
ans[i] += mu[j] * s[j] * s[j];
}
}
int T; scanf("%d", &T);
while(T --) {
int n; scanf("%d", &n);
printf("%d
", ans[n]);
}
return 0;
}