AtCoder Regular Contest E - Snuke Line
解法
とても重要な事実として、M以下のxの倍数を、x=1..Mについて列挙すると、その数はM logMくらいになります。
自然数xのM以下の倍数の数はM/x個なので、これをx=1..Mについて全て足し合わせると、以下のようないい加減な見積もりにより求まります。
よって、各dについてdの倍数を全て列挙しても大丈夫そうです。
dの時の答えを求めるには、各区間の累積和を作っておいて、dのとき、2dのとき、3dのとき、...と足し合わせていきたいところですが、kdのときに数えた区間を、(k+1)dのときにも数えてしまわないようにしたいです。
kdのときに数えた区間を、(k+1)dのときにも数えてしまうような区間は、長さがdより大きい区間ですが、そのような区間は数えるまでもなく必ず通るはずなので、dの時に数える区間は長さがd以下の区間に限れば良いです。
コード
import java.io.PrintWriter; import java.util.ArrayList; import java.util.Scanner; @SuppressWarnings("unchecked") public class Main { private void solve(Scanner in, PrintWriter out) { int N = in.nextInt(); int M = in.nextInt(); FenwickTree bit = new FenwickTree(M + 2); int[] l = new int[N]; int[] r = new int[N]; ArrayList<Integer>[] buckets = new ArrayList[M + 1]; for (int i = 1; i <= M; i++) { buckets[i] = new ArrayList<>(); } for (int i = 0; i < N; i++) { l[i] = in.nextInt(); r[i] = in.nextInt(); int w = r[i] - l[i] + 1; buckets[w].add(i); } int gone = 0; for (int d = 1; d <= M; d++) { for (int i : buckets[d]) { gone++; bit.add(l[i], 1); bit.add(r[i] + 1, -1); } int ans = N - gone; for (int m = d; m <= M; m += d) { ans += bit.sum(m + 1); } out.println(ans); } } public class FenwickTree { int N; long[] data; FenwickTree(int N) { this.N = N + 1; data = new long[N + 1]; } void add(int k, long val) { for (int x = k; x < N; x |= x + 1) { data[x] += val; } } // [0, k) long sum(int k) { if (k >= N) { k = N - 1; } long ret = 0; for (int x = k - 1; x >= 0; x = (x & (x + 1)) - 1) { ret += data[x]; } return ret; } } public static void main(String[] args) { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); new Main().solve(in, out); in.close(); out.close(); } }