結果

問題 No.473 和と積の和
ユーザー 37zigen
提出日時 2016-12-24 19:13:24
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,690 ms / 3,000 ms
コード長 1,371 bytes
コンパイル時間 3,891 ms
コンパイル使用メモリ 78,268 KB
実行使用メモリ 349,460 KB
最終ジャッジ日時 2024-12-16 05:10:13
合計ジャッジ時間 20,878 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;

import java.util.*;

public class Q473 {
	static int n;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int x = sc.nextInt();
		++x;
		int[] div = new int[10000];
		int pos = 0;
		for (int i = 1; i * i <= x; ++i) {
			if (x % i == 0) {
				div[pos++] = i;
				if (i * i != x) {
					div[pos++] = x / i;
				}
			}
		}
		div = Arrays.copyOf(div, pos);
		Arrays.sort(div);
		map = new long[pos][pos + 1][n + 1];
		for (int i = 0; i < map.length; ++i) {
			for (int j = 0; j < map[i].length; ++j) {
				for (int k = 0; k < map[i][j].length; ++k) {
					map[i][j][k] = -1;
				}
			}
		}
		System.out.println(dfs(x, div, 1, 0));
	}

	static long[][][] map;

	static long dfs(int cur, int[] div, int pos, int count) {
		if (map[Arrays.binarySearch(div, cur)][pos][count] != -1) {
			return map[Arrays.binarySearch(div, cur)][pos][count];
		}
		if (count == n) {
			if (cur == 1)
				return 1;
			else
				return 0;
		}
		if (div.length == pos || count >= n)
			return 0;
		else {
			long ret = 0;
			if (cur % div[pos] == 0) {
				ret += dfs(cur / div[pos], div, pos, count + 1);
			}
			ret += dfs(cur, div, pos + 1, count);
			map[Arrays.binarySearch(div, cur)][pos][count] = ret;
			return ret;
		}
	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}
0