TopCoder SRM 640 Div1 Hard TwoNumberGroups

これ想定解は何なんだろう…。
http://community.topcoder.com/stat?c=problem_statement&pm=13525

問題

Div2 Hard同様、同一要素の重複を含む整数の集合S,Tが与えられる。

ここで関数f(n)を考える。
f(n)はnの絶対値の素因数となる素数の和を示す。

を求めよ。

解法

結局f(A[i]-B[j])の総和を求めることになる。
安直に求めるには|A[i]-B[j]|を素因数分解すればよいが、|A|,|B|の上限は1000であり、10^6回の素因数分解は素数の事前計算では間に合わない。
ミラーラビン判定も作ってみたが間に合わなかった。

そこでもう少し違ったアプローチが必要になる。
ある素数pに対し、A[i]及びB[j]をA[i]%p、B[j]%pの値で分類する。
A[i]%p及びB[j]%pが一致するA[i],B[j]は差がpで割れるので、解にnumA[i]*numB[j]*pを加えればよい。

max(A)は10^9なので、pは√10^9程度までの素数を試せばよい。
pが大きくなるほどA[i]%p、B[j]%pの値はばらつくのでA[i]-B[j]がpで割れるケースは減少するため、計算が間に合うことになる。

ll mo=1000000007;
const int prime_max = 35000;
int NP,prime[10000],divp[prime_max];

vector<int> V[2][100001];
int dif[1001][1001];

void cprime() {
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		prime[NP++]=i;
		for(int j=i;j<prime_max;j+=i) divp[j]=i;
	}
}

class TwoNumberGroups {
	public:
	int solve(vector <int> A, vector <int> numA, vector <int> B, vector <int> numB) {
		int i,j,x,y;
		
		NP=0;
		ZERO(divp);
		cprime();
		FOR(x,A.size()) FOR(y,B.size()) dif[x][y]=abs(A[x]-B[y]);
		
		ll ret=0;
		FOR(i,NP) {
			int p=prime[i];
			
			FOR(x,A.size()) V[0][A[x]%p].push_back(x);
			FOR(x,B.size()) V[1][B[x]%p].push_back(x);
			FOR(j,p) {
				if(V[0][j].size() && V[1][j].size()) {
					ITR(it,V[0][j]) ITR(it2,V[1][j]) if(dif[*it][*it2]>1) {
						ret = (ret + 1LL*numA[*it]*numB[*it2]%mo*p)%mo;
						while(dif[*it][*it2]%p==0) dif[*it][*it2]/=p;
					}
				}
				V[0][j].clear();
				V[1][j].clear();
			}
		}
		FOR(x,A.size()) FOR(y,B.size()) if(dif[x][y]>1) ret=(ret+1LL*dif[x][y]*numA[x]%mo*numB[y])%mo;
		
		return ret%mo;
	}
}

まとめ

この問題multisetにする意味あったのかな…？
numA、numBのパラメータほとんど意味ないぞ。