ABC - 052 - C

AtCoder - ABC - C

C

• 注
  • 自分で解いてみた過程を備忘として書いているので大分おかしい点が多いのはスルーして

C問題は、N!の正の約数の個数を 10^9+7 で割った余り

単純に考えると、以下になります。
1.N!を求める
2.N!の約数の個数を求める
3.約数の個数を10^9+7で割って余りを求める

1.N!を求める

		long CONST = (long) Math.pow(10, 9) + 7;
		int numN = nextInt();

		long res = 1;
		for (int i = 1; i <= numN; i++) {
			res *= i;
		}

2.N!の約数の個数を求める
参考：約数の個数

		long result = 1;
		for (int i = 2; i <= kaijou; i++) {
			//約数
			int yakusu = 0;
			while (kaijou % i == 0) {
				yakusu++;
				kaijou /= i;
			}
			if (yakusu != 0) {
				result *= (yakusu + 1);
			}
		}

3.約数の個数を10^9+7で割って余りを求める

CONST = Math.pow(10,9)+7

out.println(result % CONST);

とやってみると、N=3,6なんかはACできます。

ただ、N=1000が問題です。
1000!だと途中で桁あふれが起きます。

1000!を出力してみました（あっているかは知らん）

402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

です。
longのようなprimitiveでは扱えません。BigDecimalで何とか出力しました。

ということで、力技を使います。
数値を全てBigDecimalで扱ってみます。

		long CONST = (long) Math.pow(10, 9) + 7;
		int numN = nextInt();

		BigDecimal kaijou = BigDecimal.ONE;
		for (int i = 1; i <= numN; i++) {
			kaijou = kaijou.multiply(new BigDecimal(i));
		}

		BigDecimal result = BigDecimal.ONE;
		BigDecimal index = new BigDecimal("2");
		BigDecimal lKaijou = new BigDecimal(kaijou.toString());
		while (index.compareTo(lKaijou) < 0) {

			//約数
			BigDecimal yakusu = BigDecimal.ZERO;
			while (kaijou.remainder(index).equals(BigDecimal.ZERO)) {
				yakusu = yakusu.add(BigDecimal.ONE);
				kaijou = kaijou.divide(index);
			}
			if (!yakusu.equals(BigDecimal.ZERO)) {
				yakusu = yakusu.add(BigDecimal.ONE);
				result = result.multiply(yakusu);
			}
			index = index.add(BigDecimal.ONE);
		}

		out.println(result.remainder(new BigDecimal(CONST)));

これで桁あふれによるエラーはなくなりましたが、そもそも2秒以内に終わりません。
ということで、このアプローチはダメ。

解消しなくてはいけないのは以下。

• 扱う値が大きすぎる(N!を格納できるprimitiveがない)
• 時間がかかる(N!にしてから計算するので計算量が多い)
• そもそも、N!を先に求めるから桁あふれる。N!の約数の個数なので、1 - Nそれぞれの約数の個数を足せばよいはず。そうすれば、N!を計算する必要がなくなる。

		long CONST = (long) Math.pow(10, 9) + 7;
		int numN = nextInt();

		long res = 1;
		//全てを合算してからではオーバーフローするので、各値を素因数分解して合計とする。
		Map<Integer, Integer> wkMap = new HashMap<Integer, Integer>();
		for (int i = 2; i <= numN; i++) {
			int temp = i;
			int yakusu = 0;
			for (int j = 2; j <= i;) {
				if (temp % j == 0) {
					yakusu++;
					temp /= j;
				} else {
					if (yakusu != 0) {
						wkMap.merge(j, yakusu, (x, y) -> x + y);
					}
					j++;
					yakusu = 0;
				}
			}
		}

で、最後に約数の個数を求めてmod

		for (Integer b : wkMap.values()) {
			res = (b + 1) * res;
		}

		out.println(res);

ハイ失敗。resがlongなんですが、桁あふれです。
ですから、力技

		for (Integer b : wkMap.values()) {
			res = res.multiply(new BigDecimal(b).add(BigDecimal.ONE));
		}
		out.println(res.remainder(new BigDecimal(CONST)));

これで通ります。www
もう少し頭を使ってみます。最後まで乗算してから剰余を求めるからあふれる。途中で剰余を求められばよい。

		//すべてを合算してから余りを求めるとオーバーフローするので
		//合計のmodは各値のmodの責に等しいを利用
		for (Integer b : wkMap.values()) {
			res = ((b + 1) * res) % CONST;
		}

		out.println(res);

すっきりしたか。