結果
問題 |
No.28 末尾最適化
|
ユーザー |
|
提出日時 | 2017-01-06 15:23:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 838 ms / 5,000 ms |
コード長 | 2,204 bytes |
コンパイル時間 | 1,168 ms |
コンパイル使用メモリ | 94,780 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-17 14:32:19 |
合計ジャッジ時間 | 2,201 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 2 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <map>#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)using ll = long long;using namespace std;template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }vector<int> sieve_of_eratosthenes(int n) { // enumerate primes in [2,n] with O(n log log n)vector<bool> is_prime(n+1, true);is_prime[0] = is_prime[1] = false;for (int i = 2; i*i <= n; ++i)if (is_prime[i])for (int k = i+i; k <= n; k += i)is_prime[k] = false;vector<int> primes;for (int i = 2; i <= n; ++i)if (is_prime[i])primes.push_back(i);return primes;}map<int,int> prime_factrorize(int n, vector<int> const & primes) {map<int,int> result;for (int p : primes) {if (n < p * p) break;while (n % p == 0) {result[p] += 1;n /= p;}}if (n != 1) result[n] += 1;return result;}const int inf = 1e9+7;int main() {int q; cin >> q;while (q --) {int seed, n, k, b; cin >> seed >> n >> k >> b;map<int,int> ps = prime_factrorize(b, sieve_of_eratosthenes(b));vector<vector<int> > xs;for (int x = seed; xs.size() < n+1; x = x *(ll) (x + 12345) % 100000009 + 1) {int y = x;xs.emplace_back();for (auto it : ps) {int p = it.first;xs.back().push_back(0);while (y % p == 0) { ++ xs.back().back(); y /= p; }}}int ans = inf;repeat (p,ps.size()) {partial_sort(xs.begin(), xs.begin() + k, xs.end(), [&](vector<int> const & x, vector<int> const & y) { return x[p] < y[p]; });vector<int> t(ps.size());repeat (i,k) repeat (j,ps.size()) t[j] += xs[i][j];int j = 0;for (auto it : ps) {int cnt = it.second;setmin(ans, t[j] / cnt);++ j;}}cout << ans << endl;}return 0;}