Divan and Kostomuksha（性质+dp+优化转移方程）
Divan and Kostomuksha
[Link](Problem - D1 - Codeforces)
题意
给你
n
n
n个数，
a
1
,
a
2
,
.
.
.
,
a
n
a_1,a_2,...,a_n
a1,a2,...,an。你可以将这
n
n
n个数随意摆放，问你
∑
i
=
1
n
g
c
d
(
a
1
,
a
2
,
.
.
.
,
a
i
)
sum_{i=1}^{n}gcd(a_1,a_2,...,a_i)
∑i=1ngcd(a1,a2,...,ai)的最大值是多少？
数据范围：
1
≤
n
≤
1
0
5
1le nle 10^5
1≤n≤105，
1
≤
m
=
m
a
x
(
a
i
)
≤
5
×
1
0
6
1le m=max(a_i) le 5times10^6
1≤m=max(ai)≤5×106，时限
4
s
4s
4s
思路
假设我们将
a
i
=
x
a_i=x
ai=x放到了第一个位置，那么后面一定是先放
x
x
x的倍数最优，这样
(
x
,
a
i
(
x
的
倍
数
)
)
=
=
x
(x,a_i(x的倍数))==x
(x,ai(x的倍数))==x，否则的话
(
x
,
a
i
(
不
是
x
的
倍
数
)
)
=
=
d
(
x
的
因
数
)
(x,a_i(不是x的倍数))==d(x的因数)
(x,ai(不是x的倍数))==d(x的因数)，所以先放
x
x
x的倍数贡献最大。放完
x
x
x的倍数以后再放别的就会让
g
c
d
gcd
gcd减少，设接下来放完的
g
c
d
=
=
y
gcd==y
gcd==y，那么
y
∣
x
y|x
y∣x，发现好像有转移关系。
设
f
[
x
]
；
最
开
始
g
c
d
位
x
的
满
足
题
意
的
最
大
值
f[x]；最开始gcd位x的满足题意的最大值
f[x]；最开始gcd位x的满足题意的最大值，一开始为
x
x
x放完倍数再放就会使
g
c
d
gcd
gcd变成
x
x
x的一个因数
y
y
y，看一下
f
[
x
]
和
f
[
y
]
f[x]和f[y]
f[x]和f[y]是否有递推式。
设
c
n
t
[
i
]
：
有
多
少
个
i
的
倍
数
cnt[i]：有多少个i的倍数
cnt[i]：有多少个i的倍数，因为
y
∣
x
y|x
y∣x所以
c
n
t
[
x
]
∈
c
n
t
[
y
]
cnt[x]in cnt[y]
cnt[x]∈cnt[y]，
f
[
y
]
f[y]
f[y]的最优解的形式为
y
+
y
的
倍
数
(
c
n
t
[
y
]
个
，
包
含
x
和
x
的
倍
数
)
+
其
它
→
x
+
x
的
倍
数
(
c
n
t
[
x
]
个
)
+
y
+
y
的
倍
数
(
c
n
t
[
y
]
−
c
n
t
[
x
]
个
)
+
其
他
y+y的倍数(cnt[y]个，包含x和x的倍数)+其它to x+x的倍数(cnt[x]个)+y+y的倍数(cnt[y]-cnt[x]个)+其他
y+y的倍数(cnt[y]个，包含x和x的倍数)+其它→x+x的倍数(cnt[x]个)+y+y的倍数(cnt[y]−cnt[x]个)+其他。因此
f
[
x
]
=
f
[
y
]
+
(
x
−
y
)
×
c
n
t
[
x
]
f[x]=f[y]+(x-y)times cnt[x]
f[x]=f[y]+(x−y)×cnt[x]，即原来跟在
y
y
y后面
g
c
d
gcd
gcd为
y
y
y的移到前面
g
c
d
gcd
gcd可以多
y
−
x
y-x
y−x，一共有
c
n
t
[
x
]
cnt[x]
cnt[x]个。
状态表示：
f
[
i
]
:
g
c
d
以
i
开
头
的
最
大
s
u
m
f[i]:gcd以i开头的最大sum
f[i]:gcd以i开头的最大sum
状态转移：
f
[
i
]
=
m
a
x
(
f
[
j
]
+
(
i
−
j
)
×
c
n
t
[
i
]
∣
j
∣
i
)
f[i]=max(f[j]+(i-j)times cnt[i] |j|i)
f[i]=max(f[j]+(i−j)×cnt[i] ∣j∣i)
每个数的倍数可以读入的时候直接调和级数统计大概
O
(
n
l
o
g
m
)
O(nlogm)
O(nlogm)，转移可以直接暴力枚举值域调和级数向它倍数转移复杂度
O
(
m
l
o
g
m
)
O(mlogm)
O(mlogm)可以卡过。
Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <unordered_map>
#include <cmath>
#include <stack>
#include <iomanip>
#include <deque>
#include <sstream>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 5e6 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
#define tpyeinput int
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
LL cnt[N];
LL f[N];
LL res;
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n;
for (int i = 0; i < n; i ++) {
int x; cin >> x;
cnt[x] ++;
}
for (int i = 1; i <= N; i ++)
for (int j = i + i; j <= N; j += i)
cnt[i] += cnt[j];
f[1] = n;
for (int i = 1; i <= N; i ++) {
res = max(res, f[i]);
for (int j = i + i; j <= N; j += i)
f[j] = max(f[j], f[i] + (j - i) * cnt[j]);
}
cout << res << endl;
return 0;
}
D2
[Link](Problem - D2 - Codeforces)
题意
不变
数据范围：
1
≤
n
≤
1
0
5
1le nle 10^5
1≤n≤105，
1
≤
m
=
m
a
x
(
a
i
)
≤
2
×
1
0
7
1le m=max(a_i) le 2times10^7
1≤m=max(ai)≤2×107，时限
4
s
4s
4s
思路
延续上次思路
O
(
m
l
o
g
m
)
O(mlogm)
O(mlogm)，铁
T
T
T。
考虑优化，对于统计每个数的倍数我们可以用试除法
O
(
n
n
)
O(nsqrt n)
O(nn
)来枚举每个数的约数来统计。
对于我们的状态转移，我们的做法是每个数都往他的倍数转移，发现每个数往它的素数倍转移时最优的。
证明
设有
i
i
i且
j
=
x
i
j=xi
j=xi且
x
不
是
素
数
x不是素数
x不是素数，那么
x
必
可
以
拆
成
x
=
k
（
素
数
）
×
x
2
x必可以拆成x=k（素数）times x_2
x必可以拆成x=k（素数）×x2。
i
i
i向
j
j
j有两种转移方式 :
i
→
j
:
f
[
j
]
=
f
[
i
]
+
(
j
−
i
)
×
c
n
t
[
j
]
ito j :f[j]=f[i]+(j-i)times cnt[j]
i→j:f[j]=f[i]+(j−i)×cnt[j]
i
→
k
→
j
：
f
[
j
]
=
f
[
i
]
+
(
k
−
i
)
×
c
n
t
[
k
]
+
(
j
−
k
)
×
c
n
t
[
j
]
ito k to j：f[j]=f[i]+(k-i)times cnt[k]+(j-k)times cnt[j]
i→k→j：f[j]=f[i]+(k−i)×cnt[k]+(j−k)×cnt[j]
=
f
[
i
]
+
j
c
n
t
[
j
]
−
i
c
n
t
[
k
]
+
k
c
n
t
[
k
]
−
k
c
n
t
[
j
]
+
i
c
n
t
[
j
]
−
i
c
n
t
[
j
]
=f[i]+jcnt[j]-icnt[k]+kcnt[k]-kcnt[j]+icnt[j]-icnt[j]
=f[i]+jcnt[j]−icnt[k]+kcnt[k]−kcnt[j]+icnt[j]−icnt[j]
=
f
[
i
]
+
(
j
−
i
)
×
c
n
t
[
j
]
+
(
i
−
k
)
×
(
c
n
t
[
j
]
−
c
n
t
[
k
]
)
=f[i]+(j-i)times cnt[j]+(i-k)times (cnt[j]-cnt[k])
=f[i]+(j−i)×cnt[j]+(i−k)×(cnt[j]−cnt[k])
因为
c
n
t
[
j
]
≥
c
n
t
[
k
]
,
k
≥
i
cnt[j]ge cnt[k],kge i
cnt[j]≥cnt[k],k≥i 所以第一种转移没有用，一次我们只需要枚举每个数的素数和倍即可。
玄学复杂度
O
(
C
l
o
g
l
o
g
c
)
O(Cloglogc)
O(Cloglogc)
Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <unordered_map>
#include <cmath>
#include <stack>
#include <iomanip>
#include <deque>
#include <sstream>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 2e7 + 1, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
#define tpyeinput int
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}
int n, m, k;
LL cnt[N];
LL f[N];
int primes[N], idx;
bool st[N];
void get_primes(int n) {
for (int i = 2; i <= n; i ++) {
if (!st[i]) primes[idx ++] = i;
for (int j = 0; primes[j] <= n / i; j ++) {
st[primes[j]*i] = true;
if (i % primes[j] == 0) break;
}
}
}
int main() {
get_primes(N - 1);
scanf("%d", &n);
for (int i = 0; i < n; i ++) {
int x; scanf("%d", &x);
for (int j = 1; j * j <= x; j ++)
if (x % j == 0) {
cnt[j] ++;
if (j != x / j) cnt[x/j] ++;
}
}
f[1] = n;
LL res = 0;
for (int i = 1; i < N; i ++) {
res = max(res, f[i]);
for (int j = 0; j < idx && primes[j] * i < N; j ++) {
int p = primes[j];
f[i * p] = max(f[i * p], f[i] + (p * i - i) * cnt[p * i]);
}
}
printf("%lldn", res);
return 0;
}