Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-03SRM350, SRM351, SRM352 (Practice)

SRM 350 SumsOfPerfectPowers

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

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

  • 求めるべき数の中で、m >= 2 で a^m となってる数はそんなに多くない。
    • なので、全て列挙し、2つの数の組み合わせを全部試せる。
import java.util.HashSet;
import java.util.Set;

public class SumsOfPerfectPowers {
	int MAX = 8000000;
	
	public int howMany(int lowerBound, int upperBound) {
		boolean[] done = new boolean[MAX];
		Set<Integer> l = new HashSet<Integer>();
		
		for (int a = 0 ; a <= 10000 ; a++) {
			long aa = a;
			for (int m = 2 ; m <= 100 ; m++) {
				aa *= a;
				if (aa >= MAX || aa <= -1) {
					break;
				}
				l.add((int)aa);
			}
		}

		int cnt = 0;
		boolean[] met = new boolean[MAX];
		for (int a : l) {
			for (int b : l) {
				int ab = a + b;
				if (lowerBound <= ab && ab <= upperBound) {
					if (!met[ab]) {
						met[ab] = true;
						cnt++;
					}
				}
			}
		}
		return cnt;
	}
}