結果
問題 | No.368 LCM of K-products |
ユーザー |
![]() |
提出日時 | 2020-01-07 22:24:54 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 557 ms / 2,000 ms |
コード長 | 3,642 bytes |
コンパイル時間 | 2,506 ms |
コンパイル使用メモリ | 172,400 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-23 01:15:47 |
合計ジャッジ時間 | 21,034 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define int long long #define FOR(i, a, b) for(int i=(a);i<(b);i++) #define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--) #define REP(i, n) for(int i=0; i<(n); i++) #define RREP(i, n) for(int i=(n-1); i>=0; i--) #define ALL(a) (a).begin(),(a).end() #define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end()); #define CONTAIN(a, b) find(ALL(a), (b)) != (a).end() #define array2(type, x, y) array<array<type, y>, x> #define vector2(type) vector<vector<type> > #define out(...) //printf(__VA_ARGS__) int dxy[] = {0, 1, 0, -1, 0}; void solve(); signed main() { #if DEBUG std::ifstream in("input.txt"); std::cin.rdbuf(in.rdbuf()); #endif cin.tie(0); ios::sync_with_stdio(false); solve(); return 0; } /*================================*/ template<int MOD> struct ModInt { static const int Mod = MOD; unsigned x; ModInt() : x(0) { } ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; } ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; } int get() const { return (int)x; } ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; } ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; } ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; } ModInt &operator/=(ModInt that) { return *this *= that.inverse(); } ModInt operator+(ModInt that) const { return ModInt(*this) += that; } ModInt operator-(ModInt that) const { return ModInt(*this) -= that; } ModInt operator*(ModInt that) const { return ModInt(*this) *= that; } ModInt operator/(ModInt that) const { return ModInt(*this) /= that; } ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); } return ModInt(u); } bool operator==(ModInt that) const { return x == that.x; } bool operator!=(ModInt that) const { return x != that.x; } ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; } }; template<int MOD> ostream& operator<<(ostream& st, const ModInt<MOD> a) { st << a.get(); return st; }; template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) { ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; } typedef ModInt<1000000007> mint; int N,K; vector<int> primes; int A[1000]; void solve() { cin>>N>>K; REP(i,N)cin>>A[i]; primes.push_back(2); for(int i=3; i<1e5; i+=2) { int is_prime = true; for (int p : primes) { if (i%p==0) { is_prime = false; break; } } if (is_prime) primes.push_back(i); } // primes.size => 9592 map<int, vector<int>> M; REP(i,N) { int a = A[i]; out("%lld:\n", a); for (int p : primes) { if (p > a) break; int k=0; while(a%p==0) { k++; a/=p; } if (k) { out(" %lld ^ %lld = %lld\n", p, k, (int)pow(p,k)); M[p].push_back(k); } } if (a > 1) { out(" %lld ^ %d = %lld\n", a, 1, a); M[a].push_back(1); } } mint ans = mint(1); for (auto p : M) { auto vec = p.second; sort(ALL(vec), greater<int>()); REP(i,min(K,(int)vec.size())) { ans *= mint(p.first) ^ vec[i]; } } cout << ans << endl; }