yukicoder : No.2046 Ans Mod? Mod Ans!

これは余り迷わなかったな。
https://yukicoder.me/problems/no/2046

問題

互いに異なる正整数からなる数列Aが与えられる。
2要素の対(i,j)において、|(A[i] % A[j]) - (A[j] % A[i])|の総和を求めよ。

A[i]＜A[j]とすると、この値は(A[i] - A[j]%A[i])となる。
Aを昇順にソートした場合、iに対し

• A[i]*(N-i)分だけ解に加算し、
• i＜jであるhに対しsum(A[j]%A[i])だけ解から減算する

という処理を行えばよい。
前者は容易で、問題は後者。

A[j]%A[i] = A[j]-floor(A[j]/A[i])*A[i]である。
よって、BITを用いて、floor(A[j]/A[i])=Xとなるjの個数Yとsum(A[j])を高速に求められるようにしておけば、Xを総当たりしながらsum(A[j]) - Y*X*A[i]を求めて行けばよい。
A[i]がdistinctであることから、考えるべきXの個数は高々O(max(A)*log(max(A))程度である。

int N;
ll A[202020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> num,sum;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		num.add(A[i],1);
		sum.add(A[i],A[i]);
	}
	ll ret=0;
	FOR(i,N) {
		x=A[i];
		ret+=(num(200000)-num(x))*x;
		for(y=1;x*y<=200000;y++) {
			ll k=num(x*(y+1)-1)-num(x*y-1);
			ll s=sum(x*(y+1)-1)-sum(x*y-1);
			ret-=s;
			ret+=k*y*x;
		}
	}
	cout<<ret<<endl;
}
||,

*まとめ