对于一个x我们发现最多只有 \(\log\) 次有效取模，但没啥用。我们发现 \(dp\) 数组(函数)是一个分段一次函数(等差数列)，然后从第一个 \(a_i\) 开始考虑，发现每次只会多出一条线段(就是\(a_i-1\)这条)其他线段会翻折到下面，对于一条线段只会进行\(\log a\)次翻折，所以对线段的操作总次数是\(n \log a\)的，上个\(map\)就能做到\(n \log n \log a\)了
点击查看代码
bool M1;
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<" MB\n"
#define look_time cerr<<(clock()-Time)*1.0/CLOCKS_PER_SEC<<'\n'
#include <cstdio>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <cstring>
#include <array>
#include <algorithm>
#include <queue>
#include <vector>
#include <bitset>
#include <ctime>
#include <cstdlib>
#include <random>
#include <set>
#include <ctime>
#include <map>
#include <stack>
#include <unordered_map>
#include <assert.h>
#include <unordered_set>
#define i128 __int128
#define ll long long
#define uint unsigned
#define ull unsigned long long
#define ld long double
#define fo(a,b,c) for(ll a=b;a<=c;++a)
#define re(a,b,c) for(ll a=b;a>=c;--a)
#define pii pair<ll,ll>
#define pdd pair<db,db>
#define fi first
#define pb push_back
#define se second
#define ite set<ll> ::iterator
#define vite vector<ll> ::iterator
#define mite map<ll,ll> ::iterator
using namespace std;
const ll mod=1e9+7;
inline ll gi()
{
ll x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x * f;
}
ll _=1;
const ll inf=2e17+5,iinf=1e9+5;
const ll N=200005;
ll n,a[N];
map<ll,ll> mp;
void ckmax(ll &x,ll y)
{
if(x<y) x=y;
}
void sol()
{
n=gi();
fo(i,1,n) a[i]=gi();
mp[a[1]-1]=0;
fo(i,2,n)
{
while(1)
{
mite it=mp.lower_bound(a[i]);
if(it==mp.end()) break;
mp.erase(it);
pii p=*it;
ll num=p.fi/a[i];
ckmax(mp[a[i]-1],p.se+(num-1)*a[i]*(i-1));
ckmax(mp[p.fi%a[i]],p.se+num*a[i]*(i-1));
}
}
ll ans=0;
for(pii p:mp)
{
ans=max(ans,p.se+p.fi*n);
}
cout<<ans;
}
bool M2;
int main()
{
int Time=clock();
look_memory;
// _=gi();
while(_--)
{
sol();
printf("\n");
}
look_time;
return 0;
}