結果
問題 | No.1532 Different Products |
ユーザー | 👑 tatyam |
提出日時 | 2021-05-17 20:07:08 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,640 ms / 4,000 ms |
コード長 | 4,411 bytes |
コンパイル時間 | 3,780 ms |
コンパイル使用メモリ | 234,132 KB |
実行使用メモリ | 50,232 KB |
最終ジャッジ日時 | 2024-04-27 03:48:37 |
合計ジャッジ時間 | 73,559 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
7,292 KB |
testcase_01 | AC | 767 ms
45,440 KB |
testcase_02 | AC | 30 ms
19,780 KB |
testcase_03 | AC | 15 ms
21,176 KB |
testcase_04 | AC | 15 ms
15,284 KB |
testcase_05 | AC | 8 ms
17,188 KB |
testcase_06 | AC | 101 ms
30,528 KB |
testcase_07 | AC | 179 ms
33,628 KB |
testcase_08 | AC | 215 ms
38,936 KB |
testcase_09 | AC | 394 ms
46,312 KB |
testcase_10 | AC | 720 ms
47,488 KB |
testcase_11 | AC | 637 ms
47,184 KB |
testcase_12 | AC | 1,043 ms
49,020 KB |
testcase_13 | AC | 691 ms
49,808 KB |
testcase_14 | AC | 1,531 ms
49,392 KB |
testcase_15 | AC | 235 ms
49,600 KB |
testcase_16 | AC | 1,034 ms
44,248 KB |
testcase_17 | AC | 613 ms
47,928 KB |
testcase_18 | AC | 503 ms
48,832 KB |
testcase_19 | AC | 980 ms
49,144 KB |
testcase_20 | AC | 1,445 ms
49,740 KB |
testcase_21 | AC | 1,151 ms
45,560 KB |
testcase_22 | AC | 776 ms
48,864 KB |
testcase_23 | AC | 537 ms
49,684 KB |
testcase_24 | AC | 1,398 ms
49,532 KB |
testcase_25 | AC | 1,087 ms
47,960 KB |
testcase_26 | AC | 464 ms
43,664 KB |
testcase_27 | AC | 1,283 ms
46,356 KB |
testcase_28 | AC | 1,000 ms
46,720 KB |
testcase_29 | AC | 1,256 ms
44,048 KB |
testcase_30 | AC | 1,419 ms
47,144 KB |
testcase_31 | AC | 1,427 ms
47,400 KB |
testcase_32 | AC | 1,450 ms
47,924 KB |
testcase_33 | AC | 1,357 ms
46,992 KB |
testcase_34 | AC | 1,414 ms
49,048 KB |
testcase_35 | AC | 1,447 ms
48,080 KB |
testcase_36 | AC | 1,502 ms
48,568 KB |
testcase_37 | AC | 1,165 ms
41,188 KB |
testcase_38 | AC | 1,492 ms
49,156 KB |
testcase_39 | AC | 1,456 ms
48,652 KB |
testcase_40 | AC | 1,433 ms
48,768 KB |
testcase_41 | AC | 1,622 ms
50,144 KB |
testcase_42 | AC | 1,540 ms
49,680 KB |
testcase_43 | AC | 1,545 ms
49,964 KB |
testcase_44 | AC | 1,606 ms
49,960 KB |
testcase_45 | AC | 1,582 ms
50,116 KB |
testcase_46 | AC | 1,569 ms
49,992 KB |
testcase_47 | AC | 1,592 ms
50,112 KB |
testcase_48 | AC | 1,590 ms
50,104 KB |
testcase_49 | AC | 1,592 ms
50,140 KB |
testcase_50 | AC | 1,640 ms
50,144 KB |
testcase_51 | AC | 1,592 ms
50,188 KB |
testcase_52 | AC | 1,575 ms
50,152 KB |
testcase_53 | AC | 1,595 ms
50,088 KB |
testcase_54 | AC | 1,581 ms
49,996 KB |
testcase_55 | AC | 1,624 ms
50,192 KB |
testcase_56 | AC | 1,578 ms
49,932 KB |
testcase_57 | AC | 1,580 ms
50,084 KB |
testcase_58 | AC | 1,599 ms
50,040 KB |
testcase_59 | AC | 1,581 ms
49,796 KB |
testcase_60 | AC | 1,610 ms
50,232 KB |
testcase_61 | AC | 2 ms
6,940 KB |
testcase_62 | AC | 3 ms
6,944 KB |
testcase_63 | AC | 1,569 ms
50,116 KB |
ソースコード
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; using u32 = uint32_t; using u64 = uint64_t; vector<bool> sieve_of_atkin(int N){ vector<bool> isprime(N + 1); const int sqrtN = sqrt(N); int n; for(int z = 1; z <= 5; z += 4) for(int y = z; y <= sqrtN; y += 6){ for(int x = 1; x <= sqrtN && (n = 4*x*x+y*y) <= N; ++x) isprime[n] = !isprime[n]; for(int x = y+1; x <= sqrtN && (n = 3*x*x-y*y) <= N; x += 2) isprime[n] = !isprime[n]; } for(int z = 2; z <= 4; z += 2) for(int y = z; y <= sqrtN; y += 6){ for(int x = 1; x <= sqrtN && (n = 3*x*x+y*y) <= N; x += 2) isprime[n] = !isprime[n]; for(int x = y+1; x <= sqrtN && (n = 3*x*x-y*y) <= N; x += 2) isprime[n] = !isprime[n]; } for(int y = 3; y <= sqrtN; y += 6) for(int z = 1; z <= 2; ++z){ for(int x = z; x <= sqrtN && (n = 4*x*x+y*y) <= N; x += 3) isprime[n] = !isprime[n]; } for(int n = 5; n <= sqrtN; ++n) if(isprime[n]) for(int k = n*n; k <= N; k+=n*n) isprime[k] = false; isprime[2] = isprime[3] = true; return isprime; } vector<u32> primes(int N){ auto isprime = sieve_of_atkin(N); vector<u32> ans; for(int i = 2; i <= N; i++) if(isprime[i]) ans.push_back(i); return ans; } int main(){ u32 N; u64 K; cin >> N >> K; if(K == 1) return puts("1") & 0; const vector<u32> P = primes(N); // log を取ってナップサック DP // 整数に丸めた時の誤差が小さくなるマジックナンバー constexpr long double num = 260012.54060995877246L; const u32 lgK = round(logl(K) * num); vector<u32> lg(N + 1); // log の概算値 num 倍して、整数に丸める for(u32 i : P) lg[i] = round(logl(i) * num); for(u32 p : P) for(u32 i = 2; i * p <= N; i++) lg[i * p] = lg[i] + lg[p]; // ナップサック DP vector<u64> dp(lgK + 1); dp[0] = 2; for(u32 i = 2; i <= N; i++){ const u32 x = lg[i]; for(u32 i = lgK; i >= x; i--) dp[i] += dp[i - x]; } // このままだと、K 以下が入っていなかったり K より大きいのが入っていたりする // K より大きいのが入らないように狭める dp.resize(lgK - 2); u64 ans = accumulate(dp.begin(), dp.end(), -1LL); // K 以下で入っていないものを追加する auto solve = [N](u64 x) -> u32 { // 積が x になる個数を x の約数上の DP で求める unordered_map, map は遅いのでソート済み列の merge を使う vector<pair<u64, u32>> dp = {{1, 2}}; for(u32 j = 2; j <= N; j++) if(x % j == 0){ auto update = [x, j](pair<u64, u32>& a){ a.first *= j; if(a.first < x && x % a.first) a.first = 0; }; vector<pair<u64, u32>> dp2; u32 p = 0, q = 0; while(q < dp.size()){ if(dp[q].first == 0){ q++; continue; } if(p < dp.size()){ if(p == q || dp[p].first < dp[q].first){ dp2.push_back(dp[p]); update(dp[p]); p++; } else if(dp[p].first == dp[q].first){ dp2.emplace_back(dp[p].first, dp[p].second + dp[q].second); update(dp[p]); p++; q++; } else{ dp2.push_back(dp[q]); q++; } continue; } if(dp[q].first > x) break; dp2.push_back(dp[q]); q++; } swap(dp, dp2); } if(dp.back().first != x) return 0; return dp.back().second; }; // K 以下で入っていないものを追加する for(u64 i = max<int64_t>(2, K - 1e6); i <= K; i++){ u64 x = i; u32 y = 0; // 素因数分解してチェック for(u32 p : P) while(x % p == 0){ x /= p; y += lg[p]; } if(y >= dp.size()) ans += solve(i); } cout << ans << endl; }