和后缀和。

bk=∑i|kai

bk=∑k|dad

都一样，没啥区别。

前缀和的写法：

for( auto &p: primes ) 
    for( int j = 1; 1LL * j * p <= N; j ++ ) 
        b[ j * p ] += a[j];

后缀和翻过来就行。

一种比较野蛮的办法是参见 Sum over Subsets DP 的证明，这个东西实际上就是以质数为轴的高维前缀和。

另一种是循环不等式，没看懂。

这里考虑证明前缀和的形式，后缀和同理：

令 pi 表示从小到大第 i 个质数，假设 Si,j={x|x=k⋅j∧k=∑i=1ppiai(ai∈N)}

我们令在第 k 轮结束后，bi=∑j∈Si,jai。

在 k=0 显然成立。

在 k≠0 时，如果 pk|i ，令 i′=ipk，则有

bi=bi+bi′=∑j∈Sk–1,iaj+∑j∈Sk,ikaj∵Sk–1,i∩Sk,i′=∅,Sk–1,i∪Sk,i′=Sk,i∴bi=bi+bi′=∑j∈Sk,iaj

则如果在 k−1(k>0) 时成立，则在 k 时成立。

容易发现这么做复杂度和埃氏筛一样，O(nlog⁡log⁡n)

3 例 Codeforces 1614 D Divan and Kostomuksha

给定数组 a，求任意重排后最大化 ∑i=1nf(i)，其中 f(1)=a1,f(i)=gcd(f(i–1),ai)。

n≤1e5。两档，ai≤5×106,ai≤2×107。

令 pi=∑j[ajmodi=0],
gi 表示当前构造序列中所有数字的 gcd=ki(k∈N) 时，能够得到的最大 ∑if(i)，
m=maxa。

容易得到： gi=maxi|dfd+(pi–pd)×i

很容易得到 ∑imi=O(nlog⁡(n)) 的做法，能过第一档，考虑优化。

瓶颈在两处，求 pi 和 gi。

pi 直接使用 Dirichlet 后缀。

注意到可以 gi 递推式可以改善：

令 si 表示为 i 的质因子集合，则有 gi=maxj∈sifd+(pi–pd)×i，其中 d=ij。

容易发现可以直接套用埃氏筛。

总复杂度 O(nlog⁡log⁡n)。

/*
 * d2.cpp
 * Copyright (C) 2022 Woshiluo Luo <[email protected]>
 *
 * 「Two roads diverged in a wood,and I—
 * I took the one less traveled by,
 * And that has made all the difference.」
 *
 * Distributed under terms of the GNU AGPLv3+ license.
 */

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <vector>
#include <algorithm>

typedef const int cint;
typedef long long ll;
typedef unsigned long long ull;

inline bool isdigit( const char cur ) { return cur >= '0' && cur <= '9'; }/*{{{*/
template <class T> 
T Max( T a, T b ) { return a > b? a: b; }
template <class T> 
T Min( T a, T b ) { return a < b? a: b; }
template <class T> 
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T> 
void chk_Min( T &a, T b ) { if( b < a ) a = b; }
template <typename T>
T read() { 
    T sum = 0, fl = 1; 
    char ch = getchar();
    for (; isdigit(ch) == 0; ch = getchar())
        if (ch == '-') fl = -1;
    for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
    return sum * fl;
}
template <class T> 
T pow( T a, int p ) {
    T res = 1;
    while( p ) {
        if( p & 1 ) 
            res = res * a;
        a = a * a;
        p >>= 1;
    }
    return res;
}/*}}}*/

const int N = 2e7 + 10;

int pool[N]; 
ll f[N];

std::vector<int> primes;
bool is_prime[N];

void pre() {
    memset( is_prime, true, sizeof(is_prime) );
    for( int i = 2; i < N; i ++ ) {
        if( is_prime[i] ) 
            primes.push_back(i);
        for( auto &x: primes ) {
            if( 1LL * x * i >= N ) 
                break;
            is_prime[ x * i ] = false;
            if( i % x == 0 ) 
                break;
        }
    }
}

int main() {
#ifdef woshiluo
    freopen( "d2.in", "r", stdin );
    freopen( "d2.out", "w", stdout );
#endif
    pre();

    cint n = read<int>();
    for( int i = 1; i <= n; i ++ ) 
        pool[ read<int>() ] ++;
    for( auto &p: primes ) {
        for( int j = ( N - 1 ) / p; j >= 1; j -- ) {
            pool[j] += pool[ j * p ];
        }
    }

    ll ans = 0;
    for( int i = N - 1; i >= 1; i -- ) {
        chk_Max( f[i], 1LL * pool[i] * i );
        for( auto &p: primes ) {
            if( 1LL * i * p >= N ) 
                break;
            cint nxt = i * p;
            chk_Max( f[i], f[nxt] + 1LL * ( pool[i] - pool[nxt] ) * i );
        }
        chk_Max( ans, f[i] );
    }

    printf( "%lld\n", ans );
}

class

OI

local_offer

Codeforces

local_offer

dp

local_offer

数学

发表评论 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注