yukicoder : No.1233 割り切れない気持ち

お手頃な問題。
https://yukicoder.me/problems/no/1233

問題

N要素の整数列Aが与えられる。
1≦i,j≦Nに対し、A[i]%A[j]の総和を求めよ。

解法

まず各値の登場回数を覚えておく。
また、Aを昇順にソートしたうえで累積和を取っておく。

今、A[j]がある値vであるときを考え、A[i]%vの総和を考える。
A[i]%v=A[i]-floor(A[i]/v)なので、Aを昇順にソートした数列にlower_boundを適用すると、非負整数kに対しv*k≦A[i]＜v*(k+1)であるようなA[i]の区間がわかるので、累積和を使えばそれらの総和が容易にわかる。
A[j]が小さい値ばかりだと調べるkの総和が増えるが、同じ値のものはまとめて処理することでTLEを防ぐことができる。

int N;
int A[202020];
ll S[202020];
int num[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		num[A[i]]++;
	}
	sort(A,A+N);
	FOR(i,N) S[i+1]=S[i]+A[i];
	ll ret=0;
	for(i=1;i<=200000;i++) if(num[i]) {
		for(x=0,y=0;y<=200000;y+=i) {
			int z=lower_bound(A,A+N,y+i)-A;
			
			ret+=num[i]*((S[z]-S[x])-1LL*(z-x)*y);
			x=z;
		}
	}
	
	cout<<ret<<endl;
	
	
}

まとめ

1年以上前に作られた問題なのか…。