- 给定一个长度为(n)的数组(a_{1sim n})，定义(f(i,x)=egin{cases}x\%a_i+f(i+1,x\%a_i)&(i<n)\x\%a_n&(i=n)end{cases})。
- 对所有正整数(x)，求(f(1,x))的最大值。
- (nle2 imes10^5,a_ile10^{13})
寻找关键点
容易发现，如果(x)在模过(a_{1sim i})之后不为(0)，那么(x-1)在模(a_{1sim i})的过程中始终恰好比(x)小(1)。
也就是说，我们可以写出一个函数(i imes x+b)表示模(a_i)余(1sim Mx)的数一种可能的贡献，并把(Mx)称作一个关键点。
那么每(DP)到一个位置(i)，原本的关键点依然是关键点（可能要经过取模），而(a_{i}-1)则成为了一个新的关键点。
又由于一个数取模一次至少会减半，一个关键点最多取模(O(logV))次，所以即便我们每次枚举关键点暴力取模，总共也只会有(O(nlogV))次操作。
动态规划
设(f_{i,x})表示当前(DP)到第(i)位，对于关键点(x)，函数(i imes x+b)中(b)的最大值。
转移只需找出大于等于(a_i)的那些关键点，分别考虑它们取模后的变化以及对新关键点(a_{i}-1)的贡献，得到：
[f_{i,x\%a_i}=f_{i-1,x}+(i-1) imes(x-x\%a_i)\
f_{i,a_i-1}=f_{i-1,x}+(i-1) imes(lfloorfrac{x-(a_i-1)}{a_i}
floor imes a_i)
]
本题中可以使用(map)优化。
代码：(O(nlognlogV))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Rg register
#define RI Rg int
#define Cn const
#define CI Cn int&
#define I inline
#define W while
#define N 200000
#define LL long long
using namespace std;
int n;LL a[N+5];map<LL,LL> P;map<LL,LL>::iterator it;
int main()
{
RI i;for(scanf("%d",&n),i=1;i<=n;++i) scanf("%lld",a+i);
for(P[a[1]-1]=0,i=2;i<=n;++i) for(it=P.lower_bound(a[i]);it!=P.end();P.erase(it++))//枚举大于等于a[i]的关键点
P[it->first%a[i]]=max(P[it->first%a[i]],it->second+(i-1)*(it->first-it->first%a[i])),//考虑取模后的变化
P[a[i]-1]=max(P[a[i]-1],it->second+(i-1)*((it->first-(a[i]-1))/a[i]*a[i]));//考虑对新关键点a[i]-1的贡献
LL t=0;for(it=P.begin();it!=P.end();++it) t=max(t,n*it->first+it->second);return printf("%lld
",t),0;//枚举所有关键点统计最终答案
}