結果

問題 No.854 公平なりんご分配
ユーザー yakamotoyakamoto
提出日時 2019-07-26 22:51:28
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 1,245 ms / 3,153 ms
コード長 3,734 bytes
コンパイル時間 1,707 ms
コンパイル使用メモリ 171,444 KB
実行使用メモリ 123,180 KB
最終ジャッジ日時 2023-09-15 03:30:46
合計ジャッジ時間 20,398 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,384 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 4 ms
4,380 KB
testcase_23 AC 3 ms
4,380 KB
testcase_24 AC 6 ms
4,524 KB
testcase_25 AC 3 ms
4,376 KB
testcase_26 AC 6 ms
4,576 KB
testcase_27 AC 4 ms
4,608 KB
testcase_28 AC 4 ms
4,376 KB
testcase_29 AC 2 ms
4,380 KB
testcase_30 AC 4 ms
4,376 KB
testcase_31 AC 6 ms
4,688 KB
testcase_32 AC 68 ms
28,356 KB
testcase_33 AC 96 ms
16,432 KB
testcase_34 AC 178 ms
37,992 KB
testcase_35 AC 115 ms
30,540 KB
testcase_36 AC 56 ms
4,716 KB
testcase_37 AC 65 ms
26,880 KB
testcase_38 AC 48 ms
22,348 KB
testcase_39 AC 300 ms
40,036 KB
testcase_40 AC 113 ms
14,628 KB
testcase_41 AC 123 ms
24,936 KB
testcase_42 AC 148 ms
37,340 KB
testcase_43 AC 214 ms
26,044 KB
testcase_44 AC 211 ms
34,756 KB
testcase_45 AC 163 ms
9,032 KB
testcase_46 AC 296 ms
34,416 KB
testcase_47 AC 91 ms
20,564 KB
testcase_48 AC 128 ms
36,744 KB
testcase_49 AC 113 ms
37,540 KB
testcase_50 AC 53 ms
26,452 KB
testcase_51 AC 286 ms
35,952 KB
testcase_52 AC 166 ms
17,404 KB
testcase_53 AC 75 ms
17,132 KB
testcase_54 AC 162 ms
19,852 KB
testcase_55 AC 44 ms
17,340 KB
testcase_56 AC 41 ms
17,808 KB
testcase_57 AC 76 ms
14,980 KB
testcase_58 AC 132 ms
7,756 KB
testcase_59 AC 34 ms
13,268 KB
testcase_60 AC 111 ms
14,900 KB
testcase_61 AC 41 ms
5,200 KB
testcase_62 AC 120 ms
12,996 KB
testcase_63 AC 83 ms
13,524 KB
testcase_64 AC 27 ms
7,120 KB
testcase_65 AC 82 ms
33,056 KB
testcase_66 AC 67 ms
10,948 KB
testcase_67 AC 121 ms
22,228 KB
testcase_68 AC 110 ms
11,152 KB
testcase_69 AC 65 ms
40,364 KB
testcase_70 AC 37 ms
15,204 KB
testcase_71 AC 46 ms
15,900 KB
testcase_72 AC 75 ms
4,980 KB
testcase_73 AC 61 ms
27,156 KB
testcase_74 AC 146 ms
32,708 KB
testcase_75 AC 79 ms
16,016 KB
testcase_76 AC 105 ms
25,924 KB
testcase_77 AC 113 ms
36,540 KB
testcase_78 AC 161 ms
11,936 KB
testcase_79 AC 156 ms
23,072 KB
testcase_80 AC 145 ms
24,268 KB
testcase_81 AC 92 ms
24,932 KB
testcase_82 AC 522 ms
122,820 KB
testcase_83 AC 700 ms
123,180 KB
testcase_84 AC 944 ms
122,864 KB
testcase_85 AC 765 ms
122,860 KB
testcase_86 AC 487 ms
122,824 KB
testcase_87 AC 527 ms
122,868 KB
testcase_88 AC 526 ms
122,932 KB
testcase_89 AC 525 ms
122,996 KB
testcase_90 AC 524 ms
122,816 KB
testcase_91 AC 525 ms
122,936 KB
testcase_92 AC 1,243 ms
122,856 KB
testcase_93 AC 1,245 ms
122,876 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#ifndef SOLUTION_COMMON_H

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using PI = pair<int, int>;
template<class T> using V = vector<T>;
using VI = V<int>;
#define _1 first
#define _2 second

#ifdef MY_DEBUG
# define DEBUG(x) x
#else
# define DEBUG(x)
#endif

template<class T>
inline void debug(T &A) {
  DEBUG(
      for (const auto &a : A) {
        cerr << a << " ";
      }
      cerr << '\n';
  )
}

template<class T, class Func>
inline void debug_with_format(T &A, Func f) {
  DEBUG(
      for (const auto &a : A) {
        cerr << f(a) << " ";
      }
      cerr << '\n';
  )
}

template<class T>
inline void debug_dim2(T &A) {
  DEBUG(
      for (const auto &as : A) {
        debug(as);
      }
  )
}

template<typename ... Args>
inline void debug(const char *format, Args const &... args) {
  DEBUG(
      fprintf(stderr, format, args ...);
      cerr << '\n';
  )
}

template<typename ... Args>
string format(const string &fmt, Args ... args) {
  size_t len = snprintf(nullptr, 0, fmt.c_str(), args ...);
  vector<char> buf(len + 1);
  snprintf(&buf[0], len + 1, fmt.c_str(), args ...);
  return string(&buf[0], &buf[0] + len);
}

template<class T1, class T2>
string fmtP(pair<T1, T2> a) {
  stringstream ss;
  ss << "(" << a._1 << "," << a._2 << ")";
  return ss.str();
}

#define SOLUTION_COMMON_H

#endif //SOLUTION_COMMON_H


class PrimeFactorization {
public:
  VI prime, factor;

  PrimeFactorization(int MAX): factor(MAX + 1) {
    for (int i = 2; i <= MAX; ++i) {
      if (factor[i] == 0) {
        factor[i] = i;
        prime.push_back(i);
      }

      int p = 0;
      while (p < prime.size() && prime[p] * i <= MAX) {
        factor[prime[p] * i] = prime[p];
        if (prime[p] == i) break;
        p++;
      }
    }
  }
};

const int MOD = 1000000007;

class D {
public:
  void solve(std::istream& in, std::ostream& out) {
    int N;
    in >> N;
    VI A(N);
    for (int i = 0; i < N; ++i) {
      in >> A[i];
    }

    int MAX = 2000;
    PrimeFactorization pf(MAX);
    int m = pf.prime.size();

    VI rev(MAX + 1);
    for (int i = 0; i < m; ++i) {
      rev[pf.prime[i]] = i;
    }

    VI zero(N + 1);
    V<VI> dp(m, VI(N + 1));
    for (int i = 0; i < N; ++i) {
      if (A[i] == 0) {
        zero[i + 1]++;
      } else {
        int x = A[i];
        while(x > 1) {
          int p = pf.factor[x];
          dp[rev[p]][i + 1]++;
          x /= p;
        }
      }
    }

    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < m; ++j) {
        dp[j][i + 1] += dp[j][i];
      }
      zero[i + 1] += zero[i];
    }

    int Q;
    in >> Q;
    for (int t = 0; t < Q; ++t) {
      int P, L, R;
      in >> P >> L >> R;
      L--;R--;
      bool ok = true;
      if (zero[R + 1] > zero[L]) {
        // 途中に0があるので必ず割り切れる
        ok = true;
      } else {
        VI cnt(m); // 素因数ごとの個数
        while(ok && P > 1) {
          bool all = false;
          for (int i = 0; i < m; ++i) {
            if (P % pf.prime[i] == 0) {
              P /= pf.prime[i];
              cnt[i]++;
              all = true;
              break;
            }
          }
          if (!all) ok = false;
        }
        debug(cnt);
        for (int i = 0; i < m; ++i) {
          int c = dp[i][R + 1] - dp[i][L];
          ok = ok && cnt[i] <= c;
          debug("cnt[i]:%d c:%d", cnt[i], c);
        }
      }
      out << (ok ? "Yes" : "NO") << '\n';
    }
  }
};


int main() {
	D solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}
0