結果
問題 |
No.368 LCM of K-products
|
ユーザー |
![]() |
提出日時 | 2016-07-05 00:26:27 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 4,948 bytes |
コンパイル時間 | 1,249 ms |
コンパイル使用メモリ | 113,000 KB |
実行使用メモリ | 17,536 KB |
最終ジャッジ日時 | 2024-09-22 14:50:26 |
合計ジャッジ時間 | 2,798 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
#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; }