Hatena::Grouptopcoder

kuuso1の日記

2014-12-28

SRM643 div1Easy TheKingsFactorization

| 05:07 | SRM643 div1Easy  TheKingsFactorization - kuuso1の日記 を含むブックマーク はてなブックマーク - SRM643 div1Easy  TheKingsFactorization - kuuso1の日記

http://community.topcoder.com/stat?c=problem_statement&pm=13594

  • 与えられたN を素因数分解し、素因数を昇順に全列挙した配列を返す。ex) N=12 → return {2,2,3}
  • ヒントとして 答えの奇数番目を抜き出した配列 primes が与えられる。 ex) N=12 → primes = {2,3}

(制約)2 ≤ N ≤ 1e18

方針:単純に与えられたNを素因数分解しようとすると、O(√N) となり、1e9 オーダーなのでTLEする。

primesで与えられている数でNを割っていけばNは小さくなるが、例えば 2 × デカい素数 みたいな場合はいずれにしてもO(√N)から改善しない。

以下のような考察で、1e6 以下の素因数について求められれば良い。

f:id:kuuso1:20141229052559p:image

コードは以下。計算量は O(logN * N^(1/3)) くらい。logNは素因数の個数をおさえるオーダー。

primes[i-1] ≤ x ≤ primes[i] で丁寧に探索範囲を絞るのをサボっています(篩つかってるのでそんなに変わらない筈)

using System;
using System.Collections.Generic;
public class TheKingsFactorization {
	public long[] getVector(long N, long[] primes) {
		int NN=1000000;
		int[] P=new int[NN];//エラトステネスの篩
		for(int i=2;i<NN;i++){
			if(P[i]==0){
				for(int j=i+i;j<NN;j+=i)P[j]=1;
			}
		}

		List<long> L=new List<long>();
		for(int i=0;i<primes.Length;i++){
			N/=primes[i];
			L.Add(primes[i]);
		}
		while(true){   //みつかるだけ1e6以下の素因数をみつける
			bool chk=false;
			for(int i=2;i<NN;i++){
				if(P[i]==0 && N%i==0){
					N/=i;
					L.Add(i);
					chk=true;
					break;
				}
			}
			if(!chk)break;
		}
		if(N!=1)L.Add(N);
		L.Sort();
		return L.ToArray();
	}
}

本番は分からずprimes[i-1] ≤ x ≤ primes[i] なるxをすべて探しに行くコードを書いて(xがデカい素数の場合がコーナー)challengeで10秒でしゅんころされました。div1怖い。

まぁそれはそれとして、無理してデカい素数を直接突き止めなくても、わかる範囲で周りを固めていけば最後に全貌が分かるというのがなかなか良い問題だと思ったので日記に書いておきます。