結果
問題 | No.2262 Fractions |
ユーザー | 👑 Nachia |
提出日時 | 2023-04-07 23:36:01 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 348 ms / 2,000 ms |
コード長 | 6,283 bytes |
コンパイル時間 | 1,165 ms |
コンパイル使用メモリ | 91,128 KB |
実行使用メモリ | 5,920 KB |
最終ジャッジ日時 | 2024-05-05 07:25:27 |
合計ジャッジ時間 | 15,160 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 203 ms
5,248 KB |
testcase_01 | AC | 230 ms
5,376 KB |
testcase_02 | AC | 219 ms
5,376 KB |
testcase_03 | AC | 216 ms
5,376 KB |
testcase_04 | AC | 223 ms
5,376 KB |
testcase_05 | AC | 229 ms
5,376 KB |
testcase_06 | AC | 214 ms
5,376 KB |
testcase_07 | AC | 211 ms
5,376 KB |
testcase_08 | AC | 210 ms
5,376 KB |
testcase_09 | AC | 207 ms
5,376 KB |
testcase_10 | AC | 209 ms
5,376 KB |
testcase_11 | AC | 241 ms
5,376 KB |
testcase_12 | AC | 232 ms
5,376 KB |
testcase_13 | AC | 238 ms
5,376 KB |
testcase_14 | AC | 247 ms
5,376 KB |
testcase_15 | AC | 244 ms
5,376 KB |
testcase_16 | AC | 252 ms
5,376 KB |
testcase_17 | AC | 245 ms
5,376 KB |
testcase_18 | AC | 244 ms
5,376 KB |
testcase_19 | AC | 291 ms
5,376 KB |
testcase_20 | AC | 262 ms
5,376 KB |
testcase_21 | AC | 293 ms
5,376 KB |
testcase_22 | AC | 265 ms
5,376 KB |
testcase_23 | AC | 227 ms
5,376 KB |
testcase_24 | AC | 321 ms
5,792 KB |
testcase_25 | AC | 337 ms
5,912 KB |
testcase_26 | AC | 327 ms
5,792 KB |
testcase_27 | AC | 325 ms
5,912 KB |
testcase_28 | AC | 322 ms
5,656 KB |
testcase_29 | AC | 322 ms
5,792 KB |
testcase_30 | AC | 322 ms
5,916 KB |
testcase_31 | AC | 332 ms
5,792 KB |
testcase_32 | AC | 348 ms
5,920 KB |
testcase_33 | AC | 335 ms
5,892 KB |
testcase_34 | AC | 338 ms
5,784 KB |
testcase_35 | AC | 320 ms
5,912 KB |
testcase_36 | AC | 332 ms
5,916 KB |
testcase_37 | AC | 334 ms
5,916 KB |
testcase_38 | AC | 336 ms
5,784 KB |
testcase_39 | AC | 275 ms
5,376 KB |
testcase_40 | AC | 276 ms
5,376 KB |
testcase_41 | AC | 279 ms
5,376 KB |
testcase_42 | AC | 281 ms
5,376 KB |
testcase_43 | AC | 281 ms
5,376 KB |
testcase_44 | AC | 323 ms
5,792 KB |
testcase_45 | AC | 339 ms
5,788 KB |
ソースコード
#line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\divisor-convolution.hpp" #line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\prime-sieve-explicit.hpp" #include <vector> #include <algorithm> #include <cassert> #include <iostream> namespace nachia{ namespace prime_sieve_explicit_internal{ std::vector<bool> isprime = { false }; // a[x] := isprime(2x+1) void CalcIsPrime(int z){ if((int)isprime.size() *2+1 < z+1){ int new_z = isprime.size(); while(new_z*2+1 < z+1) new_z *= 2; z = new_z-1; isprime.resize(z+1, true); for(int i=1; i*(i+1)*2<=z; i++) if(isprime[i]){ for(int j=i*(i+1)*2; j<=z; j+=i*2+1) isprime[j] = false; } } } std::vector<int> prime_list = {2}; int prime_list_max = 0; void CalcPrimeList(int z){ while((int)prime_list.size() < z){ if((int)isprime.size() <= prime_list_max + 1) CalcIsPrime(prime_list_max + 1); for(int p=prime_list_max+1; p<(int)isprime.size(); p++){ if(isprime[p]) prime_list.push_back(p*2+1); } prime_list_max = isprime.size() - 1; } } void CalcPrimeListUntil(int z){ if(prime_list_max < z){ CalcIsPrime(z); for(int p=prime_list_max+1; p<(int)isprime.size(); p++){ if(isprime[p]) prime_list.push_back(p*2+1); } prime_list_max = isprime.size() - 1; } } } bool IsprimeExplicit(int n){ using namespace prime_sieve_explicit_internal; if(n == 2) return true; if(n % 2 == 0) return false; CalcIsPrime(n); return isprime[(n-1)/2]; } int NthPrimeExplicit(int n){ using namespace prime_sieve_explicit_internal; CalcPrimeList(n); return prime_list[n]; } int PrimeCountingExplicit(int n){ using namespace prime_sieve_explicit_internal; if(n < 2) return 0; CalcPrimeListUntil(n); auto res = std::upper_bound(prime_list.begin(), prime_list.end(), n) - prime_list.begin(); return (int)res; } // [l, r) std::vector<bool> SegmentedSieveExplicit(long long l, long long r){ assert(0 <= l); assert(l <= r); long long d = r - l; if(d == 0) return {}; std::vector<bool> res(d, true); for(long long p=2; p*p<=r; p++) if(IsprimeExplicit(p)){ long long il = (l+p-1)/p, ir = (r+p-1)/p; if(il <= p) il = p; for(long long i=il; i<ir; i++) res[i*p-l] = false; } if(l < 2) for(long long p=l; p<2 && p<r; p++) res[l-p] = false; return res; } } // namespace nachia #line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\divisor-convolution.hpp" #line 8 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\divisor-convolution.hpp" namespace nachia{ template<class Elem> void DivisorZeta(std::vector<Elem>& a){ using namespace prime_sieve_explicit_internal; int n = a.size() - 1; for(int d=2; d<=n; d++) if(IsprimeExplicit(d)) for(int i=1; i*d<=n; i++) a[i*d] += a[i]; } template<class Elem> void DivisorInvZeta(std::vector<Elem>& a){ using namespace prime_sieve_explicit_internal; int n = a.size() - 1; for(int d=2; d<=n; d++) if(IsprimeExplicit(d)) for(int i=n/d; i>=1; i--) a[i] += a[i*d]; } template<class Elem> void DivisorMobius(std::vector<Elem>& a){ using namespace prime_sieve_explicit_internal; int n = a.size() - 1; for(int d=2; d<=n; d++) if(IsprimeExplicit(d)) for(int i=n/d; i>=1; i--) a[i*d] -= a[i]; } template<class Elem> void DivisorInvMobius(std::vector<Elem>& a){ using namespace prime_sieve_explicit_internal; int n = a.size() - 1; for(int d=2; d<=n; d++) if(IsprimeExplicit(d)) for(int i=1; i*d<=n; i++) a[i] -= a[i*d]; } template<class Elem> std::vector<Elem> GcdConvolution(std::vector<Elem> a, std::vector<Elem> b){ assert(a.size() == b.size()); assert(1 <= a.size()); DivisorInvZeta(a); DivisorInvZeta(b); for(int i=1; i<(int)a.size(); i++) a[i] *= b[i]; DivisorInvMobius(a); return a; } template<class Elem> std::vector<Elem> LcmConvolution(std::vector<Elem> a, std::vector<Elem> b){ assert(a.size() == b.size()); assert(1 <= a.size()); DivisorZeta(a); DivisorZeta(b); for(int i=1; i<(int)a.size(); i++) a[i] *= b[i]; DivisorMobius(a); return a; } } #line 2 "..\\Main.cpp" #line 4 "..\\Main.cpp" #include <string> #line 7 "..\\Main.cpp" #include <atcoder/modint> using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; pair<i64,i64> testcase(){ i64 N, K; cin >> N >> K; __int128_t l = 0, r = ((__int128_t)1ll << 96) + 1; while(l+1 < r){ __int128_t m = (l+r)/2; vector<i64> cnt(N+2); for(i64 c=1; c<=N; c++){ i64 r = (m * c) >> 64; r = min(r, N); if(r > c){ cnt[c] += c; cnt[c+1] -= c-1; cnt[r+1] -= 1; } else{ cnt[c] += r; cnt[c+1] -= r; } } cnt[0] = 0; for(int i=1; i<=N; i++) cnt[i] += cnt[i-1]; nachia::DivisorMobius(cnt); i64 sumcnt = 0; for(int i=1; i<=N; i++) sumcnt += cnt[i]; //cout << "q = " << ((double)((i64)(m >> 34)) * 0x1.p-30) << endl; if(sumcnt < K) l = m; else r = m; } // l < x <= r if(l == ((__int128_t)1ll << 96)) return {-1,-1}; i64 a = N+1, b = 1; //cout << ((double)((i64)l) * 0x1.p-64) << endl; for(int i=1; i<=N; i++){ i64 q = ((__int128_t)(l * i) >> 64) + 1; if(q > N) continue; //cout << "i = " << i << " , q = " << q << endl; if(q * b < a * i){ a = q; b = i; } } return {a,b}; } int main(){ int T; cin >> T; rep(t,T){ auto ans = testcase(); if(ans.first < 0) cout << "-1\n"; else cout << ans.first << '/' << ans.second << '\n'; } return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;