結果

問題 No.368 LCM of K-products
コンテスト
ユーザー tatsukawa
提出日時 2016-05-25 15:54:50
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,803 bytes
コンパイル時間 1,735 ms
コンパイル使用メモリ 167,008 KB
実行使用メモリ 13,696 KB
最終ジャッジ日時 2024-10-07 14:10:07
合計ジャッジ時間 8,396 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

using ll=int64_t;
#define REP(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define RER(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
template<typename T> void input(T &x, size_t n) { for(int i = 0; i < n; i++) { cin >> x[i]; } }
//=====debug======
void* enabler;
#define debug(...) cout << __VA_ARGS__ << endl;
template<typename T> class has_begin_and_end { private: template<typename U> static auto check( U v ) -> decltype( v.begin(), v.end(), std::true_type() ); static auto check( ... ) -> decltype( std::false_type() ); public: typedef decltype( check( std::declval<T>() ) ) type; static bool const value = type::value; };
template<typename T> class has_top_and_pop { private: template<typename U> static auto check( U v ) -> decltype( v.empty(), v.top(), v.pop(), std::true_type() ); static auto check( ... ) -> decltype( std::false_type() ); public: typedef decltype( check( std::declval<T>() ) ) type; static bool const value = type::value; }; template<typename T>
class has_front_and_pop { private: template<typename U> static auto check( U v ) -> decltype( v.empty(), v.front(), v.pop(), std::true_type() ); static auto check( ... ) -> decltype( std::false_type() ); public: typedef decltype( check( std::declval<T>() ) ) type; static bool const value = type::value; }; 
template<class T, typename std::enable_if<has_begin_and_end<T>::value>::type*& = enabler> void output(const T& val){ auto it = val.begin(); cout << (*it++); for(; it != val.end(); ++it) cout << ' ' << (*it); cout << endl; }
template<class T, typename std::enable_if<has_top_and_pop<T>::value>::type*& = enabler> void output(T val){ while(!val.empty()){ debug(val.top()); val.pop(); } }
template<class T, typename std::enable_if<has_front_and_pop<T>::value>::type*& = enabler> void output(T val){ while(!val.empty()){ debug(val.front()); val.pop(); } }
template<class T, class U> ostream& operator<<(ostream& os, const pair<T,U>& v) { os << "(" <<  v.first <<  ", " << v.second << ")"; return os; } 

const int MOD = 1e9+7;

void extgcd(ll a, ll b, ll& x, ll& y) {
    if (b != 0) {
        extgcd(b, a%b, y, x);
        y -= a / b * x;
    }
    else {
        x = 1;
        y = 0;
    }
}

ll inv_mod(ll a, ll m) {
    ll x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}

ll res = 1LL;
ll n, k;
ll a[1024];

void dfs(int index, int count, ll val) {
    if(index == n) {
        if(count == k) {
            res = (res * inv_mod(__gcd(res, val), MOD) * val) % MOD;
        } else {
            return;
        }
    }

    for(int i = index; i < n; i++) {
        dfs(index+1, count+1, val*a[i]);
        dfs(index+1, count, val);
    }
    return;
}

int main() {
    cin >> n >> k;
    vector<ll> b;
    input(a, n);
    dfs(0, 0, 1LL);
    cout << res << endl;
}
0