TopCoderOpen 2014 Round2B Medium SumAndProductPuzzle

なんか文章の読解力を問われてるみたいだ…。
http://community.topcoder.com/stat?c=problem_statement&pm=13205

問題

２つの整数x<=yがある。
和をSusanに教え、積をPriscillaに教えた。この事実は両者知っている。
この時、以下の会話が成された。
Susan「あなたは私の数を当てられない」
Priscilla「そのヒントのおかげでわかった、あなたの数はSだ」

２値A、Bが与えられたとき、A～Bの中でSに当てはめて上記の会話が成り立つようなものを求め、その和を答えよ。

解法

x+y=S、x*y=Mとする。
Sを簡単に当てられるのは、Mが素数の場合である。
その場合、x=1、y=MとなってS=x+y=M+1の一択である。

Susanが「私の数を当てられない」というのは、x'+y'=Sとなるx',y'においてx'*y'がすべて合成数の場合である。
x'>=2の時はx'*y'は合成数なので、Susanがこう言うのは結局x'=1、y'=S-1においてy'=S-1が合成数であることを意味する。

一方Priscillaがそのヒントで答えを当てられる場合、M=x*yの候補となるx*yのうちS-1=x+y-1が１個だけ合成数で、他のx,yで素数となることを意味する。
そのようなx,yが見つかった場合、S=x+yは条件を満たすSとなる。

Bの上限値がかなり大きいため、計算を工夫して除算を避けないとTLEする。
以下のコードではMを整数で割ってx,yを求めることはせず、x,yを列挙して除算を避けている。
これでも1.2～1.7sかかる。

const int MA=5000000+50;
int divp[MA];
int comp[MA];
int samp[MA];
int ok[MA];

class SumAndProductPuzzle {
	public:
	
	long long getSum(int A, int B) {
		int i,j,k;
		
		ZERO(divp);
		ZERO(comp);
		ZERO(samp);
		ZERO(ok);
		for(i=2;i<MA;i++) if(divp[i]==0) {
			divp[i]=1;
			for(j=i*2;j<MA;j+=i) divp[j]=i;
		}
		for(i=1;i*i<MA;i++) for(j=i;i*(ll)j<MA;j++) if(divp[i+j-1]>1 && comp[i*j]<2) comp[i*j]++,samp[i*j]=i+j;
		for(i=2;i<MA;i++) if(comp[i]==1) ok[samp[i]]=1;
		ll ret=0;
		for(i=A;i<=B;i++) if(ok[i]) ret+=i;
		return ret;
		
	}
}

まとめ

問題文の理解に相当てこずる問題。
また、地味にBの上限値が凶悪で、せっかく解けたと思ってもTLEする。
幸い、入力値が単純でtestは行いやすいのだが。