TopCoder SRM 661 Div1 Easy MissingLCM

本番Easy遅いしMedium1ミスしたし出なくて結果的に正解かも。
http://community.topcoder.com/stat?c=problem_statement&pm=13766

問題

正整数Nが与えられる。
LCM(1..M)=LCM(N..M)となるN以上の最小の整数Mを求めよ。

解法

LCM(1..M)=LCM(N..M)であるには、LCM(N..M)がLCM(1..(N-1))の倍数であればよい。

まず1～(N-1)を順に素因数分解し、各素因数における指数の最大値を求めよう。
LCM(1..(N-1))の各素因数p[i]の指数の最大値をq[i]とする。
pを1～(N-1)に登場する素数列とすると、LCM(1..(N-1)) = (p[0]^q[0])*(p[1]^q[1])*... とする。
N～Mにおいて(p[0]^q[0])、(p[1]^q[1])、...、(p[i]^q[i])の各素因数の倍数が1回以上登場するまでMを増やして行けばよい。

ただ、N<=100000のためpが結構大きく、このまま上記Mを求めようとすると何かしらの工夫が必要となる。
ここでは２つの解法を紹介。

明確な素数の枝刈り

N未満の最大の素数をp[x]とする。
この場合Mは最低でも2*p[x]である。
この時、LCM(N..(2*p[x]))はp[0]～p[x]の倍数を最低1個は含む。

N～(2*p[x])は連続するNよりちょっと小さな区間なので、p[i]のうちNより大幅に小さいものは1個は登場する。
またp[x]に近い素数p[i]は(2*p[x])-Nよりは大きいかもしれないが、そのようなp[i]についても2*p[i]は概ね(2*p[x])付近にあり、N～(2*p[x])に含まれることが期待できる。

結局、LCM(N..(2*p[x]))はp[0]～p[x]の倍数を最低1個は含む。
そのためq[i]=1となるようなp[i]はLCM(N..(2*p[x]))に含まれるのが確実なので、以後は処理の対象外とできる。
よってq[i]≧2となるようなp[i]についてのみ、N～Mの間に(p[i]^q[i])が含まれるか判定していけば良い。

必要な最小値の計算

LCM(1..(N-1))が(p[i]^q[i])の積なので、N～Mは(p[i]^q[i])の倍数を含まなければならない。
(p[i]^q[i])の倍数のうちN以上の最小値は、(((N-1)/(p[i]^q[i]))+1)*(p[i]^q[i])であり、Mは最低この値でなければならない。
各iについて同様にMの最低値を求め、そのうち最大値を解とすればよい。

const int prime_max = 2100000;
int NP,prime[200000];
vector<int> divp;

void cprime() {
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		prime[NP++]=i;
		for(ll j=1LL*i*i;j>i&&j<prime_max;j+=i) divp[j]=i;
	}
}

map<ll,int> enumpr(ll n) {
	map<ll,int> V;
	
	while(divp[n]>1) {
		V[divp[n]]++;
		n/=divp[n];
	}
	if(n>1) V[n]++;
	return V;
}

class MissingLCM {
	public:
	int getMin(int N) {
		map<ll,int> MM;
		
		NP=0;
		divp.resize(prime_max);
		cprime();
		
		if(N==1) return 2;
		
		int i,mapr=0;
		for(i=1;i<=N;i++) {
			map<ll,int> v=enumpr(i);
			if(divp[i]==0) mapr=i*2;
			FORR(r,v) if(r.second>=2) MM[r.first]=max(MM[r.first],r.second);
		}
		
		for(i=N+1;;i++) {
			map<ll,int> v=enumpr(i);
			FORR(r,v) {
				if(MM.count(r.first)==0) continue;
				if(MM[r.first]<=r.second) {
					MM.erase(r.first);
				}
			}
			if(i>=mapr&&MM.empty()) return i;
		}
		return 0;
		
	}
}

まとめ

今考えると枝刈り解はだいぶ回りくどいな。