传送门：https://ac.nowcoder.com/acm/contest/8827/A
题意
$$求解\sum_{i=1}^n\sum_{j=1}^i[gcd(i,j)=1]F[j]$$ $F[j]为j各个数位之和，例如F[123]=1+2+3=6。$
思路
$前置技能：\varphi * id=\mu\;\;\;\;\mu*I=\varepsilon $ $先来看\sum_{i=1}^n\sum_{j=1}^iF[j]，可以直接等价于\sum_{i=1}^n\sum_{j=i}^nF[i]，可手动验证一下。$
$$\sum_{i=1}^n\sum_{j=1}^i[gcd(i,j)=1]F[j]$$
$$\sum_{i=1}^n\sum_{j=i}^nF[i]\sum_{di\;dj}\mu(d)$$
$枚举d：$ $$\sum_{i=1}^nF[i]\sum_{di}\mu(d)\sum_{\left \lfloor \frac{i}{d} \right \rfloor }^{\left \lfloor \frac{n}{d} \right \rfloor }1$$
$$\sum_{i=1}^nF[i]\left ( \sum_{di}\mu(d)*(\frac{n-i}{d}) \right ) $$
$$\sum_{i=1}^nF[i]\left ( \sum_{di}\mu(d)\frac{n}{d}-\sum_{di}\mu(d)\frac{i}{d}\right )$$
$设f(i)=\sum_{di}\mu(d)\frac{n}{d}，\sum_{di}\mu(d)\frac{i}{d}=\varphi，得：$
$$\sum_{i=1}^nF[i]*(f(i)-\varphi(i))$$
$\mu、\varphi、F和f预处理，然后O(n)得答案。$
Code（20MS）
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| ##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 = 1e9 + 7;
const int N = 1e6 + 10;
int mu[N], f[N], phi[N];
int F[N];
bool is_prime[N];
int prime[N];
int cnt;
int n;
int Clac(int x) {
int res = 0;
while(x) {
res += x % 10;
x /= 10;
}
return res;
}
void Init() {
mu[1] = 1;is_prime[0] = is_prime[1] = true;
for(int i = 2;i < N; i++) {
if (!is_prime[i]) {
mu[i] = -1;
phi[i] = i - 1;
prime[++cnt] = i;
}
for (int j = 1; j <= cnt && i * prime[j] < N; j++) {
is_prime[i * prime[j]] = true;
if(i % prime[j]) {
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
else {
phi[i * prime[j]] = phi[i] * prime[j];
mu[i * prime[j]] = 0;
break;
}
mu[i * prime[j]] = -mu[i];
}
}
for(int i = 1;i <= n; i++) {
F[i] = Clac(i);
for(int j = i;j <= n; j += i) {
f[j] += mu[i] * (n / i);
}
}
}
void solve() {
cin >> n;
Init();
ll ans = 0;
for(int i = 1;i <= n; i++) {
ans += 1ll * F[i] * (f[i] - phi[i]);
}
cout << ans << endl;
}
signed main() {
ios_base::sync_with_stdio(false);
##ifdef FZT_ACM_LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
signed test_index_for_debug = 1;
char acm_local_for_debug = 0;
do {
if (acm_local_for_debug == '$') exit(0);
if (test_index_for_debug > 20)
throw runtime_error("Check the stdin!!!");
auto start_clock_for_debug = clock();
solve();
auto end_clock_for_debug = clock();
cout << "Test " << test_index_for_debug << " successful" << endl;
cerr << "Test " << test_index_for_debug++ << " Run Time: "
<< double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
cout << "--------------------------------------------------" << endl;
} while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
solve();
##endif
return 0;
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/11/16/2020-ccpc-jiangxi-shengsai-a/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！