結果

問題 No.854 公平なりんご分配
ユーザー yakamoto
提出日時 2019-07-26 22:51:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,453 ms / 3,153 ms
コード長 3,734 bytes
コンパイル時間 1,860 ms
コンパイル使用メモリ 173,052 KB
実行使用メモリ 123,264 KB
最終ジャッジ日時 2024-07-02 08:48:37
合計ジャッジ時間 19,723 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 92
権限があれば一括ダウンロードができます

ソースコード

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