Divan and Kostomuksha

[Link](Problem - D1 - Codeforces)

题意

给你$n$个数， a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1​,a2​,...,an​。你可以将这$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=1n​gcd(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，时限$4s$

思路

​ 假设我们将 a i = x a_i=x ai​=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$的倍数以后再放别的就会让$gcd$减少，设接下来放完的$gcd==y$，那么$y|x$，发现好像有转移关系。

设$f[x]；最开始gcd位x的满足题意的最大值$，一开始为$x$放完倍数再放就会使$gcd$变成$x$的一个因数$y$，看一下$f[x]和f[y]$是否有递推式。

设$cnt[i]：有多少个i的倍数$，因为$y|x$所以$cnt[x]\in cnt[y]$，$f[y]$的最优解的形式为$y+y的倍数(cnt[y]个，包含x和x的倍数)+其它\to x+x的倍数(cnt[x]个)+y+y的倍数(cnt[y]-cnt[x]个)+其他$。因此$f[x]=f[y]+(x-y)\times cnt[x]$，即原来跟在$y$后面$gcd$为$y$的移到前面$gcd$可以多$y-x$，一共有$cnt[x]$个。

状态表示：$f[i]:gcd以i开头的最大sum$

状态转移：$f[i]=max(f[j]+(i-j)\times cnt[i]|j|i)$

每个数的倍数可以读入的时候直接调和级数统计大概$O(nlogm)$，转移可以直接暴力枚举值域调和级数向它倍数转移复杂度$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，时限$4s$

思路

延续上次思路$O(mlogm)$，铁$T$。

考虑优化，对于统计每个数的倍数我们可以用试除法 O ( n n ) O(nsqrt n) O(nn ​)来枚举每个数的约数来统计。

对于我们的状态转移，我们的做法是每个数都往他的倍数转移，发现每个数往它的素数倍转移时最优的。

证明

设有$i$且$j=xi$且$x不是素数$，那么 x 必 可 以 拆 成 x = k （ 素 数 ） × x 2 x必可以拆成x=k（素数）times x_2 x必可以拆成x=k（素数）×x2​。

$i$向$j$有两种转移方式 :

1. $i\to j:f[j]=f[i]+(j-i)\times cnt[j]$

2. $i\to k\to j：f[j]=f[i]+(k-i)\times cnt[k]+(j-k)\times cnt[j]$

   ​ $=f[i]+jcnt[j]-icnt[k]+kcnt[k]-kcnt[j]+icnt[j]-icnt[j]$

   ​ $=f[i]+(j-i)\times cnt[j]+(i-k)\times (cnt[j]-cnt[k])$

   因为$cnt[j]\ge cnt[k],k\ge i$ 所以第一种转移没有用，一次我们只需要枚举每个数的素数和倍即可。

玄学复杂度$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;
}