サイズ \(S\) のスライムのタイプを \(S\) の約数である最大の奇数として定めます。(すなわち \(S\) を \(2\) で割れる限り割り続けた後に得られる数です。)この時、合成前と合成後のスライムのタイプは同じであることから、あるタイプのスライムを用いて行った合成はそれ以外のタイプのスライムの数を変えず、スライムの合成はタイプごとに独立に考えることができることがわかります。

タイプ \(d\) のスライムのサイズは \(d\), \(2d\), \(4d\), \(\ldots\), \(2^kd\), \(\ldots\) です。\(k=0,1,2,\ldots\) について、サイズ \(2^kd\) のスライムが \(A_k\) 匹 (\(A_k=0\) もあり得る) いたとします。この時、タイプ \(d\) のスライムの(多重)集合に対してその 価値 を \(A_0+2A_1+4A_2+\cdots 2^kA_k+\cdots\) で定めます。この価値は合成の前後で不変です。

ここで、タイプ \(d\) のスライムの集合であって価値が \(v\) であるようなもののうちスライムの匹数が最小となるようなものを考えます。このとき(タイプ \(d\) の)どのサイズのスライムも高々 \(1\) 匹しか存在しません。なぜなら、そうでないときその集合の中から \(2\) 匹を選んで合成を行い、価値を変えずに匹数を真に減少させることができるからです。そしてそのような集合は一意に定まります。なぜなら、そのような集合は、各要素が \(0\) か \(1\) であるような整数の列 \((A_0,A_1,\ldots,A_k,\ldots)\) であって、 \(v=A_0+2A_1+4A_2+\cdots 2^kA_k+\cdots\) をみたすようなものと \(1\) 対 \(1\) に対応しますが、これは \(2\) 進数表示の一意性からただ \(1\) つ存在するからです。最後に、これは価値 \(v\) のスライムの集合から合成を繰り返す事によって達成可能です。なぜなら先に述べたように、タイプ \(d\) のスライムについてこれ以上合成を繰り返すことができなくなるまで合成を行った場合、操作の順番によらず必ずこの集合の行き着くためです。合成のたびにスライムが \(1\) 匹ずつ減少することから有限回で操作が終わる事も保証されています。

ゆえに、行うことはそのタイプのスライムが \(1\) 匹以上存在するようなタイプについて、価値を計算し、それを \(2\) 進表記したときに \(1\) であるbit の数の和を計算することです。これは mapなどでタイプの価値を管理することで、各タイプの価値の値の計算に \(O(N(\log N+\log \max(S_i)))\), 各タイプにおけるスライムの最小匹数の計算に \(O(N(\log\max(S_i)+\log \max(C_i) ))\) であるため、計算量は \(O(N(\log N+\log \max(S_i)+\log \max(C_i)))\) となります。

補足

上での説明の帰着として、スライムの(多重)集合が与えられたときそれぞれの集合から合成を行えなくなるまで行った後の集合は合成を行った順番によらず一意であり、その時スライムの数が最小となります。サイズ \(x\) 以上のスライムの合成によって、サイズ \(x\) 以下のスライムが新しく作られることはないため、スライムのサイズが小さい方から順に合成していくシミュレーションを行うことで、答えを求めることができます。順序付き集合や順序付きキューなど適当なデータ構造を使う事によって、 \(O(N(\log \max(S_i)+\log \max(C_i))\log(N(\log \max(S_i)+\log \max(C_i)))\) で答えを求めることができます。計算量は上の方針と比べて少し悪いですが、定数倍が悪い方針でなければ十分ACを獲得することができます。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int n,x,ans=0;
	long long y;
	map<int,long long>mp;
	map<int,long long>::iterator itr;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>x>>y;
		while((x&1)==0){
			x>>=1,y<<=1;
		}
		mp[x]+=y;
	}
	itr=mp.begin();
	while(itr!=mp.end()){
		y=(*itr).second;
		while(y>0){
			if(y&1)ans++;
			y>>=1;
		}
		itr++;
	}
	cout<<ans<<endl;
	return 0;
}

c++ による実装例 (補足の方針):

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int n,ans=0;
	long long x,y;
	map<long long,long long>mp;
	map<long long,long long>::iterator itr;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>x>>y;
		mp[x]+=y;
	}
	itr=mp.begin();
	while(itr!=mp.end()){
	  x=(*itr).first, y=(*itr).second;
		if(y>1)mp[2*x]+=(y/2);
		if(y&1)ans++;
		itr++;
	}
	cout<<ans<<endl;
	return 0;
}