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=1n?gcd(a1?,a2?,...,ai?)的最大值是多少？

資料范圍： 1 ≤ n ≤ 1 0 5 1\le n\le 10^5 1≤n≤105， 1 ≤ m = m a x ( a i ) ≤ 5 × 1 0 6 1\le m=max(a_i) \le 5\times10^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 1\le n\le 10^5 1≤n≤105， 1 ≤ m = m a x ( a i ) ≤ 2 × 1 0 7 1\le m=max(a_i) \le 2\times10^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(n\sqrt 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有兩種轉移方式 :

1. i → j : f [ j ] = f [ i ] + ( j ? i ) × c n t [ j ] i\to j :f[j]=f[i]+(j-i)\times cnt[j] i→j:f[j]=f[i]+(j?i)×cnt[j]

2. i → k → j ： f [ j ] = f [ i ] + ( k ? i ) × c n t [ k ] + ( j ? k ) × c n t [ j ] i\to 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],k\ge 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("%lld\n", res);
	return 0;
}