結果
問題 | No.473 和と積の和 |
ユーザー |
|
提出日時 | 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 |
ソースコード
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)); } }