Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-23SRM365 (Practice)

SRM 365 PointsOnCircle

|  SRM 365 PointsOnCircle - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 365 PointsOnCircle - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7787

  • 好きなパターンの問題(数論ゲー)きた
  • 公式が提示されてるので、それを使うんだろう
    • 最大で 4*10^18 の数の約数を数えなければならない
    • 普通にやるとTLEするので、対策を考える
  • 実験。
    • ある約数と、その二乗の約数を書きだしてみる。
      • 12 = 1, 2, 3, 4, 6, 12
      • 144 = 1, 2, 3, 4, 6, 9, 12, 16, 24, 36, 48, 72, 144
    • 二乗の約数は元の約数の何かと何かをかけ合わせた数になってるんじゃないか?
      • 36 = 6 * 6, 72 = 6 * 12, 144 = 12 * 12
    • きっとそうだ!直感的にも正しいように思える
  • 実装。
    • Setを使って重複しないように気をつけながら数え上げる
  • サンプル通った。
    • 小さめのケースでテストしようとしたがサンプルで網羅されてた
    • 大丈夫っぽい。
  • 提出
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class PointsOnCircle {

	public long count(int r) {
		long rr = 1L * r;
		long cnt1 = 0;
		long cnt3 = 0;
		List<Long> divisors = new ArrayList<Long>();
		for (long i = 1 ; i * i <= rr ; i++) {
			if (rr % i == 0) {
				divisors.add(i);
				long x = rr / i;
				if (x != i) {
					divisors.add(x);
				}
			}
		}
		
		Set<Long> dblDivisors = new HashSet<Long>();
		int dlen = divisors.size();
		for (int i = 0 ; i < dlen ; i++) {
			for (int j = 0 ; j < dlen ; j++) {
				dblDivisors.add(divisors.get(i) * divisors.get(j));
			}
		}
		
		for (long x : dblDivisors) {
			if (x % 4 == 1) {
				cnt1++;
			} else if (x % 4 == 3) {
				cnt3++;
			}
		}
		return 4L * (cnt1 - cnt3);
	}
}