#include #include #include #include #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--) #define all(x) begin(x),end(x) #define sz(x) (int)(x).size() using namespace std; using namespace atcoder; using ll=long long; using ull=unsigned long long; using ld=long double; using vll=vector; using vvll=vector; using vi=vector; using vvi=vector; using pll=pair; using pi=pair; // using mint=modint998244353; using mint=modint1000000007; // using mint2=static_modint<2>; // using BoostPoint=boost::polygon::point_data; // using Voronoi=boost::polygon::voronoi_diagram; // using mint=LazyMontgomeryModInt<998244353>; using vm=vector; using vvm=vector; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); /** * O(N) (H,T<=1e18でも解ける) * 1. 周期イベント化 * 時刻 t を、全 B_i に A_i を加算した累計回数とする * d_i=ceil(H/A_i), w_i=d_i*A_i とおく * 添字 i は時刻 d_i,2d_i,3d_i,... に必ず選ばれ * その k 回目のイベントのキーは (k*d_i,-w_i,i) となる * よって、求めるのは全イベントをキー順に並べた先頭のT個です。 * * F(t) = \sum_i floor(t/d_i) を時刻 t までのイベント数とする(実数 t>=0) * F(t) は O(N) で計算できるので、二分探索で T 番目の * イベントの時刻を求め、同時刻のイベントを処理すれば解ける (でもlog付き) * * 2. 2 段階の近似による高速化 * S = \sum_i 1/d_i を考えます(floorを無視したもの) * * 第 1 の近似:F(t) \approx t*S * t*S-N < F(t) <= t*S * 誤差は時刻 t に依存せず N 未満なので * T 番目のイベントを含む O(N) 個の候補に絞れる。 * * 第 2 の近似:S \approx P/K * S は有理数なので、正確な計算は重いため、適当な K に対して P=F(K) とする * 第 1 の近似から P/K <= S < (P+N)/K が成り立つ * つまり、O(N)時間でSを近似できる。 * * D=T+N, dmin=min_i d_i, K=D*dmin と選べば P>=D * 2 つの近似の誤差を合成して逆算すると * l=floor(T*K/(P+N)), u=floor(D*K/P) * について次が保証される * F(l) < T < F(u) * F(u)-F(l) < 2N + D*N/P <= 3N * * つまり、正確な時刻を二分探索する代わりに * T 番目を含む 3N 個未満の候補を一度に特定できる。 * * 3. 確定部分を一括計数し、残りだけ線形選択 * C_i=floor(l/d_i) は添字 i の確定済みイベント数 * R=T-\sum_i C_i 個を追加で選べば良い * * 候補は C_i>N>>H>>T; vll d(N+1),w(N+1),C(N+1); ll dmin=LLONG_MAX; rep(i,1,N+1){ ll A; cin>>A; d[i]=(H+A-1)/A; w[i]=d[i]*A; dmin=min(dmin,d[i]); } ll D=T+N,K=D*dmin,P=0; rep(i,1,N+1)P+=K/d[i]; ll l=T*K/(P+N),u=D*K/P; ll R=T; vector>events; rep(i,1,N+1){ C[i]=l/d[i]; R-=C[i]; rep(k,C[i]+1,u/d[i]+1)events.emplace_back(k*d[i],-w[i],i); } nth_element(events.begin(),events.begin()+R-1,events.end()); rep(j,0,R)C[get<2>(events[j])]++; cout<