Codeforces Round #304 Div2 D: Soldier and Number Game（素因数分解・セグメント木）

問題

codeforces.com

解法

スコアを上げるためにはできるだけ多く割り算したいので、プレイヤーはnに対して素因数分解する。なので、aの素因数の数をとすると、求める数はである。

• クエリのたびに計算すると時間がかかりすぎるので、最初にを求めておく。
• クエリのたびに計算すると時間がかかりすぎるので、がすぐに出せるようにセグメント木に入れておく。
• 入出力が非常に多いので、入力にはScannerを使わず、出力もStringBuilderに溜めておいて最後に1回だけ出力するようにする。

コード

import java.io.IOException;

public class Main {
	private final int MAX = 5000001;

	public void solve() {
		// divisor[i]:= iの約数となる最小の素数
		int[] divisor = new int[MAX];
		for (int i = 1; i < MAX; i++) {
			divisor[i] = i;
		}
		for (int i = 2; i < MAX; i++) {
			if (divisor[i] == i) {
				for (int j = i * 2; j < MAX; j += i) {
					divisor[j] = Math.min(divisor[j], i);
				}
			}
		}

		int[] primeNum = new int[MAX];
		for (int i = 2; i < MAX; i++) {
			int p = i / divisor[i];
			primeNum[i] = primeNum[p] + 1;
		}
		SegTree segTree = new SegTree(MAX);
		for (int i = 0; i < primeNum.length; i++) {
			segTree.insert(i, primeNum[i]);
		}

		int t = nextInt();
		StringBuilder sb = new StringBuilder();
		for (int test = 0; test < t; test++) {
			int a = nextInt();
			int b = nextInt();
			sb.append(segTree.sum(b + 1, a + 1));
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}

	private int nextInt() {
		int c;
		try {
			c = System.in.read();
			while (c != '-' && (c < '0' || c > '9'))
				c = System.in.read();
			if (c == '-')
				return -nextInt();
			int res = 0;
			while (c >= '0' && c <= '9') {
				res = res * 10 + c - '0';
				c = System.in.read();
			}
			return res;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return -1;
	}

	public static void main(String[] args) {
		new Main().solve();
	}
}

class SegTree {
	int N;// 最下層の子の数
	int[] seg;

	public SegTree(int N) {
		this.N = Integer.highestOneBit(N) * 2;
		seg = new int[this.N * 2 - 1];
	}

	public void insert(int position, int value) {
		position += N - 1;
		seg[position] = value;
		while (position > 0) {
			position = (position - 1) / 2;
			seg[position] = seg[position * 2 + 1] + seg[position * 2 + 2];
		}
	}

	public int sum(int a, int b) {
		return sum(a, b, 0, 0, N);
	}

	public int sum(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) {
			return 0;
		}
		if (a <= l && r <= b) {
			return seg[k];
		}
		int m = (l + r) / 2;
		return (sum(a, b, 2 * k + 1, l, m) + sum(a, b, 2 * k + 2, m, r));
	}

}