結果

問題 No.473 和と積の和
ユーザー koba-e964
提出日時 2016-12-23 03:18:55
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 2,210 ms
コード長 1,594 Byte
コンパイル時間 703 ms
使用メモリ 208,216 KB
最終ジャッジ日時 2019-09-02 17:18:43

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
a_sample1.in AC 12 ms
8,064 KB
a_sample2.in AC 11 ms
8,064 KB
a_sample3.in AC 12 ms
8,056 KB
a_sample4.in AC 418 ms
58,848 KB
b_small01.in AC 10 ms
8,064 KB
b_small02.in AC 11 ms
8,064 KB
b_small03.in AC 11 ms
8,052 KB
b_small04.in AC 14 ms
8,064 KB
b_small05.in AC 11 ms
8,052 KB
b_small06.in AC 12 ms
8,068 KB
b_small07.in AC 12 ms
8,052 KB
b_small08.in AC 12 ms
8,052 KB
b_small09.in AC 12 ms
8,068 KB
b_small10.in AC 12 ms
8,072 KB
b_small11.in AC 14 ms
8,088 KB
b_small12.in AC 15 ms
8,092 KB
b_small13.in AC 14 ms
8,092 KB
b_small14.in AC 14 ms
8,096 KB
b_small15.in AC 13 ms
8,068 KB
b_small16.in AC 12 ms
8,064 KB
b_small17.in AC 12 ms
8,048 KB
b_small18.in AC 17 ms
8,056 KB
b_small19.in AC 12 ms
8,048 KB
c_custom01.in AC 16 ms
8,680 KB
c_custom02.in AC 19 ms
9,288 KB
c_custom03.in AC 2,210 ms
208,216 KB
c_custom04.in AC 327 ms
48,360 KB
c_custom05.in AC 582 ms
72,144 KB
c_custom06.in AC 12 ms
8,052 KB
c_custom07.in AC 13 ms
8,144 KB
c_custom08.in AC 12 ms
8,132 KB
c_custom09.in AC 12 ms
8,128 KB
c_custom10.in AC 13 ms
8,116 KB
c_custom11.in AC 12 ms
8,088 KB
c_custom12.in AC 1,085 ms
114,600 KB
c_custom13.in AC 1,006 ms
108,472 KB
c_custom14.in AC 13 ms
8,188 KB
c_custom15.in AC 12 ms
8,096 KB
c_custom16.in AC 922 ms
101,932 KB
c_custom17.in AC 376 ms
52,412 KB
c_custom18.in AC 403 ms
56,116 KB
c_custom19.in AC 12 ms
8,052 KB
c_custom20.in AC 13 ms
8,196 KB
c_custom21.in AC 144 ms
25,604 KB
c_custom22.in AC 413 ms
55,764 KB
system_test1.txt AC 12 ms
8,072 KB
system_test2.txt AC 12 ms
8,068 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <unordered_map>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;

const int F = 1500;
const int N = 31;
unordered_map<ll, ll> memo[F][N];

ll solve(const VL &fact, int k, int rem, ll x) {
  if (x == 1) {
    return rem <= 0 ? 1 : 0;
  }
  if (k >= fact.size()) {
    return 0;
  }
  if (x < fact[k]) {
    return 0;
  }
  if (rem <= 0) {
    return 0;
  }
  ll f = fact[k];
  if (rem == 1) {
    return x >= f ? 1 : 0;
  }
  if (memo[k][rem].count(x)) {
    return memo[k][rem][x];
  }
  ll ret = 0;
  if (x % f == 0) {
    ret += solve(fact, k, rem - 1, x / f);
  }
  ret += solve(fact, k + 1, rem, x);
  return memo[k][rem][x] = ret;
}

int main(void){
  int n;
  ll x;
  cin >> n >> x;
  x += 1;
  if (n >= 30) {
    cout << 0 << endl;
    return 0;
  }
  VL fact;
  for (int i = 1; i * i <= x; ++i) {
    if (x % i == 0) {
      if (i > 1) {
	fact.push_back(i);
      }
      if (x != i * i) {
	fact.push_back(x / i);
      }
    }
  }
  sort(fact.begin(), fact.end());
  cout << solve(fact, 0, n, x) << endl;
}
0