这题正常的 $O(n\sqrt a_i)$ 写法我会，但是当我想尝试写一个 $O(n\log a_i)$ 的写法的时候就挂了……

因为 $j$ 已经用贪心可以确定 $j=\begin{cases} 2&i=1 \\ 1&i>1 \end{cases}$，所以对于 $x\in[1,a_i]$，设 $f(x)=\left\lfloor\dfrac{a_i}{x}\right\rfloor-a_i+a_j\times x-a_j$，$f(x)$ 会呈现一个凹函数，且 $f(x)$ 取到最小时的 $x\mid a_i$（因为当 $\left\lfloor\dfrac{a_i}{x}\right\rfloor$ 相等的时候，最小的 $a_j\times x$ 就是使 $x\mid a_i$）。

然而 Wrong answer on#7.wrong answer 1st numbers differ - expected: '3847', found: '3903'

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

const int MAXN=5e4+5,INF=0x3f3f3f3f;
int n,sum,minn,a[MAXN];

int f(int x,int i,int j){ return (a[i]+x-1)/x-a[i]+a[j]*x-a[j]; }
int calc(int i,int j){			// 三分求 f(x) 的最小值 
	int l=1,r=a[i],lm,rm,tmp;
	while(l<r){
		tmp=(r-l+2)/3; lm=l+tmp,rm=r-tmp;
		if(f(lm,i,j)<f(rm,i,j)) l=lm;
		else r=rm;
	}
	return f(l,i,j);
}
int main(){
	scanf("%d",&n); sum=minn=0;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),sum+=a[i];
	int min1=INF,min2=INF,num1,num2; 
	for(int i=1;i<=n;i++)
		if(a[i]<min1) min2=min1,num2=num1, 
					  min1=a[i],num1=i; else
		if(a[i]<min2) min2=a[i],num2=i;
	for(int i=1;i<=n;i++)
		minn=min(minn,calc(i,i==num1?num2:num1));
	printf("%d\n",sum+minn);
	return 0;
}