枚举+整除技巧
对于一个x，它的答案是
∑ni=1(⌊aix⌋+aimodx)
把取模转化为乘除运算并且整理得 ∑ni=1(ai+⌊aix⌋∗(1−x))
于是问题就变成如何快速求出 ⌊aix⌋ ，这正是我没想到的- -。我们发现随着 ai 增大， ⌊aix⌋ 是不降的，于是可以枚举取值，复杂度是log的。
附UOJ题解：http://vfleaking.blog.uoj.ac/blog/33
#include<cstdio> #define N 1000005 using namespace std; int a[N], cnt[N]; int main() { int n; long long ans=1ll<<62, sum=0; scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); cnt[a[i]]++; sum+=a[i]; } for(int i = N-2; i; i--) cnt[i]+=cnt[i+1]; for(int x = 1; x < N; x++) { long long temp=0; for(int j = 1; 1.0 * j * x < N; j++) temp+=cnt[j*x]; temp*=(1-x); temp+=sum; if(ans>temp)ans=temp; } printf("%lld\n",ans); return 0; }