牛客练习赛76 F-phi and phi 莫比乌斯反演+差分

传送门:https://ac.nowcoder.com/acm/contest/10845/F

题意

$$求解ans[i]=\sum_{i=1}^n\sum_{j=1}^n\varphi (ij)\varphi [gcd(i,j)]$$

思路

前置技能:$\varphi(ij)=\frac{\varphi(i) \varphi(j)gcd(i,j)}{\varphi[gcd(i,j)]}$

根据上式得: $$\sum_{i=1}^n\sum_{j=1}^n\varphi (i)\varphi(j)gcd(i,j)$$

$$\sum_{k=1}^nk\sum_{i=1}^n\sum_{j=1}^n\varphi (i)\varphi(j)[gcd(i,j)=k]$$

$$\sum_{k=1}^nk\sum_{i=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\sum_{j=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\varphi (ik)\varphi(jk)[gcd(i,j)=1]$$

$$\sum_{k=1}^nk\sum_{i=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\sum_{j=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\varphi (ik)\varphi(jk)\sum_{di\;dj}\mu(d)$$

交换枚举顺序:

$$\sum_{k=1}^nk\sum_{d=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\mu(d)\sum_{i=1}^{\left \lfloor \frac{n}{kd}\right \rfloor}\sum_{j=1}^{\left \lfloor \frac{n}{kd}\right \rfloor}\varphi (ikd)\varphi(jkd)$$

$$\sum_{k=1}^nk\sum_{d=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\mu(d)[\sum_{j=1}^{\left \lfloor \frac{n}{kd}\right \rfloor}\varphi (ikd)]^2$$

令T=kd并交换枚举顺序:

$$\sum_{T=1}^{n}\sum_{kT}k\mu(\frac{T}{k})[\sum_{j=1}^{\left \lfloor \frac{n}{T}\right \rfloor}\varphi (iT)]^2$$

$由\varphi = id*\mu得:$

$$\sum_{T=1}^{n}\varphi(T)[\sum_{j=1}^{\left \lfloor \frac{n}{T}\right \rfloor}\varphi (iT)]^2$$

$设f(n/T)=\sum_{j=1}^{\left \lfloor \frac{n}{T}\right \rfloor}\varphi (iT),则最终式为:$

$$ans[n]=\sum_{T=1}^n\varphi(T)[f(n/T)]^2$$

但是这题要求的是ans[1 - n],我们发现

$在枚举T时,n在[i*T,(i+1)*T)之间,\frac{n}{T}的值都一样,\varphi(T)[f(n/T)]^2的贡献不变。$

$所以我们在求ans[n]的过程中,对i*T做一个差分,最后在求一个前缀和即可。$

Code(445MS)

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
61
62
63
##pragma GCC optimize(2)
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

const int N = 1e6 + 10;

int vis[N * 3], prime[N * 3], num;
ll phi[N * 3], ans[N * 3];

void init() {
phi[1] = 1; num = 0;
for (int i = 2; i < N; i++) {
if (!vis[i]) {
prime[++num] = i; phi[i] = i - 1;
}
for (int j = 1; j <= num && i * prime[j] < N; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
}
}

void solve() {
init();
int n; scanf("%d",&n);
for(int T = 1;T <= n; T++) {
ll sum = 0;
for(int i = 1;i <= n / T; i++) {
sum = (sum + phi[i * T]) % mod;
ans[i * T] = (ans[i * T] + phi[T] * sum % mod * sum % mod + mod) % mod;
ans[(i + 1) * T] = (ans[(i + 1) * T] - phi[T] * sum % mod * sum % mod + mod) % mod;
}
}
for(int i = 1;i <= n; i++) {
ans[i] = ((ans[i] + ans[i - 1]) % mod + mod) % mod;
printf("%lld\n",ans[i]);
}
// cout << endl;
}

signed main() {
solve();
}

本文作者:jujimeizuo
本文地址https://blog.jujimeizuo.cn/2021/01/15/nowcoder-practice76-f/
本博客所有文章除特别声明外,均采用 CC BY-SA 3.0 协议。转载请注明出处!