CF889E

题目大意： 给出正整数 \(n\) 和序列 \(\{A_i\}\) ，定义 \(f_k(x) = f_{k-1}(x) \bmod a_k , f_0(x)=x\) ，求 \(\max_x{\sum_{i=1}^n f_k(x)}\) 。
\(n \le 2 \cdot 10^5 , A_i \le 10^{13}\).

首先容易发现答案的 \(x\) 一定是某个 \(A_i-1\) 。
这就可以 \(n^2\) 做了。

然后尝试把 \(n^2\) 用 DP 做，设 \(f_{i,j}\) 为做到第 \(i\) 项，\(f_i(x)=j\) 的答案。
发现所有转移都是有意义转移，不好搞。
考虑 \(x <a_i\) 的时候，贡献都是一样的，所以把贡献变为 \(i \cdot f_i(x) + b\) 的形式，此时 \(j < a_i\) 就不需要转移了。
分析取模的过程发现 \(x\) 每次“有效取模”后至多是原本的一半。
因此只会有 \(O(\log A)\) 次转移发生于此。

做完了。复杂度 \(O(n \log A \log n)\) 。

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,d) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n,m;
ll a[N];
map<ll,ll> f;
void trans(ll &a,ll b){a=(a>b?a:b);}
int main(){
	scanf("%d",&n);
	fo(i,1,n)scanf("%lld",&a[i]);
	f[a[1]-1]=0;
	fo(i,2,n){
		for(map<ll,ll>::iterator it=f.lower_bound(a[i]);it!=f.end();++it){
			trans(f[it->first % a[i]] , it->second + (ll)(i-1)*(it->first-it->first%a[i]));
			if(it->first>=a[i])trans(f[a[i]-1] , it->second + (ll)(i-1)*(it->first - it->first % a[i] -1 - (a[i]-1)));
		}
		f.erase(f.lower_bound(a[i]),f.end());
	}
	ll ans=0;
	for(auto it:f){
		trans(ans , it.second + it.first*n);
	}
	printf("%lld\n",ans);

	return 0;
}