結果
問題 | No.1330 Multiply or Divide |
ユーザー |
|
提出日時 | 2021-01-08 22:32:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,429 bytes |
コンパイル時間 | 1,508 ms |
コンパイル使用メモリ | 168,916 KB |
実行使用メモリ | 8,064 KB |
最終ジャッジ日時 | 2024-11-16 18:27:00 |
合計ジャッジ時間 | 4,789 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 WA * 2 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define chmin(x,y) x = min((x),(y)); #define chmax(x,y) x = max((x),(y)); using namespace std; using ll = long long ; using P = pair<int,int> ; using pll = pair<long long,long long>; const int INF = 1e9; const long long LINF = 1e17; const int MOD = 1000000007; //const int MOD = 998244353; const double PI = 3.14159265358979323846; int main(){ ll n,m,p; cin >> n >> m >> p; vector<ll> a(n); vector<ll> b(n); vector<ll> cnt(n,1); ll mx = 0; int mx_idx = -1; bool ok = false; rep(i,n){ cin >> a[i]; if(mx < a[i]){ mx = a[i]; mx_idx = i; } b[i] = a[i]; while(b[i]%p==0){ b[i] /= p; ++cnt[i]; } if(b[i]!=1) ok = true; } if(!ok && mx <= m){ cout << -1 << endl; return 0; } ll ans = INF; rep(i,n){ if(b[i]==1) continue; ll x = 1; ll res = 0; while(x <= m){ if(x*a[i] > m){ x *= a[i]; res ++; }else{ x *= b[i]; res += cnt[i]; } } ans = min(ans,res); res = 1; x = mx; while(x <= m){ x *= b[i]; res += cnt[i]; } ans = min(ans,res); } cout << ans << endl; return 0; }