結果
問題 | No.368 LCM of K-products |
ユーザー | tskrex |
提出日時 | 2016-07-05 00:26:27 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 74 ms / 2,000 ms |
コード長 | 4,948 bytes |
コンパイル時間 | 1,346 ms |
コンパイル使用メモリ | 112,520 KB |
実行使用メモリ | 17,792 KB |
最終ジャッジ日時 | 2023-10-23 21:19:09 |
合計ジャッジ時間 | 2,909 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
15,032 KB |
testcase_01 | AC | 19 ms
9,660 KB |
testcase_02 | AC | 3 ms
4,368 KB |
testcase_03 | AC | 8 ms
5,928 KB |
testcase_04 | AC | 13 ms
7,408 KB |
testcase_05 | AC | 74 ms
17,732 KB |
testcase_06 | AC | 2 ms
4,368 KB |
testcase_07 | AC | 3 ms
4,368 KB |
testcase_08 | AC | 2 ms
4,368 KB |
testcase_09 | AC | 3 ms
4,368 KB |
testcase_10 | AC | 2 ms
4,368 KB |
testcase_11 | AC | 2 ms
4,368 KB |
testcase_12 | AC | 2 ms
4,368 KB |
testcase_13 | AC | 28 ms
11,084 KB |
testcase_14 | AC | 48 ms
17,788 KB |
testcase_15 | AC | 51 ms
17,792 KB |
testcase_16 | AC | 47 ms
17,228 KB |
testcase_17 | AC | 34 ms
12,476 KB |
testcase_18 | AC | 52 ms
17,228 KB |
testcase_19 | AC | 13 ms
7,492 KB |
testcase_20 | AC | 32 ms
11,420 KB |
testcase_21 | AC | 9 ms
6,060 KB |
testcase_22 | AC | 50 ms
17,780 KB |
testcase_23 | AC | 2 ms
4,368 KB |
testcase_24 | AC | 2 ms
4,368 KB |
testcase_25 | AC | 2 ms
4,368 KB |
testcase_26 | AC | 2 ms
4,368 KB |
testcase_27 | AC | 2 ms
4,368 KB |
testcase_28 | AC | 2 ms
4,368 KB |
testcase_29 | AC | 2 ms
4,368 KB |
testcase_30 | AC | 2 ms
4,368 KB |
testcase_31 | AC | 2 ms
4,368 KB |
testcase_32 | AC | 2 ms
4,368 KB |
testcase_33 | AC | 21 ms
10,768 KB |
testcase_34 | AC | 3 ms
4,368 KB |
ソースコード
#include <algorithm> #include <cassert> #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <deque> #include <iomanip> #include <iostream> #include <limits> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i)) #define rep(i,n) FOR(i,0,n) #define pb push_back #define eb emplace_back #define all(v) begin(v), end(v) #define debug(x) cerr<< #x <<": "<<x<<endl #define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> i_i; typedef pair<i_i, int> p_i; typedef vector<int> vi; typedef vector<vector<int> > vvi; typedef vector<ll> vll; typedef vector<vector<ll> > vvll; typedef vector<char> vc; typedef vector<vector<char> > vvc; typedef vector<double> vd; typedef vector<vector<double> > vvd; template<class T> using vv=vector<vector< T > >; typedef deque<int> di; typedef deque<deque<int> > ddi; // cout vector template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) { int len = v.size(); for (int i = 0; i < len; ++i) { s << v[i]; if (i < len - 1) s << "\t"; } return s; } // cout 2-dimentional vector template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) { int len = vv.size(); for (int i = 0; i < len; ++i) { s << vv[i] << endl; } return s; } int MAX_PRIME; // in this problem up to 10^4.5 deque<bool> isprime; vector<int> primes; void init_prime() { isprime[0] = isprime[1] = false; for(int i = 2; i <= MAX_PRIME; i++) { if (isprime[i]) { primes.push_back(i); for(int j = i*2; j <= MAX_PRIME; j += i) isprime[j] = false; } } } template<long long M> struct ModInt { long long x; ModInt() : x(0) {} ModInt(long long y) : x(y >= 0 ? y % M : M - (-y) % M) {} ModInt &operator += (const ModInt &rhs){ if((x += rhs.x) >= M) x -= M; return *this; } ModInt &operator -= (const ModInt &rhs){ if((x += M - rhs.x) >= M) x -= M; return *this; } ModInt &operator *= (const ModInt &rhs){ x = 1LL*x*rhs.x % M; return *this; } ModInt &operator /= (const ModInt &rhs){ x = (1LL*x*rhs.inv().x) % M; return *this; } ModInt operator - () const { return ModInt(-x); } ModInt operator + (const ModInt &rhs) const { return ModInt(*this) += rhs; } ModInt operator - (const ModInt &rhs) const { return ModInt(*this) -= rhs; } ModInt operator * (const ModInt &rhs) const { return ModInt(*this) *= rhs; } ModInt operator / (const ModInt &rhs) const { return ModInt(*this) /= rhs; } bool operator < (const ModInt &rhs) const { return x < rhs.x; } ModInt inv() const { long long a = x, b = M, u = 1, v = 0, t; while(b){ t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } return ModInt(u); } ModInt pow(long long t) const { ModInt e = *this, res = 1; for(; t; e *= e, t>>=1) if(t&1) res *= e; return res; } }; template <long long M> ostream &operator << (ostream &os, const ModInt<M> &rhs){ return os << rhs.x; } template <long long M> istream &operator >> (istream &is, ModInt<M> &rhs){ long long s; is >> s; rhs = ModInt<M>(s); return is; }; int pow_mod(ll x, ll n, ll m) { ll res = 1; for (; n > 0; n >>= 1) { if (n & 1) res = (res * x) % m; x = (x * x) % m; } return res; } int main() { MAX_PRIME = sqrt(1000000000); isprime.resize(MAX_PRIME+1, true); init_prime(); int n, k; cin >> n >> k; vi a(n); vvi factors(primes.size()); map<int, int> big_primes; rep (i, n) { cin >> a[i]; } rep (i, n) { rep (j, primes.size()) { // if ( primes[j] * primes[j] > a[i] ) { // break; // } int cnt = 0; while ( a[i] % primes[j] == 0 ) { a[i] /= primes[j]; cnt += 1; } factors[j].pb(cnt); if ( a[i] == 1 ) { break; } } if ( a[i] > 1 ) { big_primes[a[i]] += 1; debug(i); } } rep (i, factors.size()) { sort(all(factors[i]), [](int x, int y) { return x > y; }); if ( factors[i].size() > k ) { factors[i].erase(begin(factors[i])+k, end(factors[i])); } } const ll mod = 1000000007; ModInt<mod> ans(1); // small primes rep (i, factors.size()) { int cnt = 0; rep (j, factors[i].size()) { cnt += factors[i][j]; } ans *= pow_mod(primes[i], cnt, mod); } // big primes for (auto bp : big_primes) { ans *= pow_mod(bp.first, min(k, bp.second), mod); } printf("%lld\n", ans.x); return 0; }