結果
問題 | No.1250 汝は倍数なりや? |
ユーザー |
|
提出日時 | 2020-10-09 21:38:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 33 ms / 1,000 ms |
コード長 | 1,514 bytes |
コンパイル時間 | 1,107 ms |
コンパイル使用メモリ | 111,100 KB |
最終ジャッジ日時 | 2025-01-15 04:12:34 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:54:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 54 | scanf("%d", &i), i = abs(i); | ~~~~~^~~~~~~~~~
ソースコード
#include <iostream> #include <algorithm> #include <map> #include <set> #include <queue> #include <stack> #include <numeric> #include <bitset> #include <cmath> static const int MOD = 1000000007; using ll = long long; using u32 = unsigned; using u64 = unsigned long long; using namespace std; template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208; vector<int> get_prime(int n){ if(n <= 1) return vector<int>(); vector<bool> is_prime(n+1, true); vector<int> prime; is_prime[0] = is_prime[1] = 0; for (int i = 2; i <= n; ++i) { if(is_prime[i]) prime.emplace_back(i); for (auto &&j : prime){ if(i*j > n) break; is_prime[i*j] = false; if(i % j == 0) break; } } return prime; } const auto primes = get_prime(65535); template<class T> map<T, int> prime_factor(T n){ map<T, int> res; for (auto &&i : primes) { while (n % i == 0){ res[i]++; n /= i; } } if(n != 1) res[n]++; return res; } int main() { int n, h; cin >> n >> h; vector<int> a(n); for (auto &&i : a) { scanf("%d", &i), i = abs(i); if(!i) return puts("YES"), 0; } auto d = prime_factor(h); for (auto &[x, p] : d) { int val = 0; for (auto &&i : a) { while(i%x == 0) { val++; i /= x; } } if(val < p) return puts("NO"), 0; } puts("YES"); return 0; }