結果
問題 | No.2262 Fractions |
ユーザー | 👑 Nachia |
提出日時 | 2023-04-08 11:17:11 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 55 ms / 2,000 ms |
コード長 | 10,725 bytes |
コンパイル時間 | 1,316 ms |
コンパイル使用メモリ | 98,584 KB |
実行使用メモリ | 7,988 KB |
最終ジャッジ日時 | 2024-05-05 07:29:42 |
合計ジャッジ時間 | 3,407 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 12 ms
6,404 KB |
testcase_01 | AC | 55 ms
5,376 KB |
testcase_02 | AC | 50 ms
5,376 KB |
testcase_03 | AC | 48 ms
5,376 KB |
testcase_04 | AC | 49 ms
5,376 KB |
testcase_05 | AC | 46 ms
5,376 KB |
testcase_06 | AC | 54 ms
5,376 KB |
testcase_07 | AC | 52 ms
5,376 KB |
testcase_08 | AC | 45 ms
5,376 KB |
testcase_09 | AC | 50 ms
5,376 KB |
testcase_10 | AC | 45 ms
5,376 KB |
testcase_11 | AC | 28 ms
5,376 KB |
testcase_12 | AC | 30 ms
5,376 KB |
testcase_13 | AC | 29 ms
5,376 KB |
testcase_14 | AC | 30 ms
5,376 KB |
testcase_15 | AC | 28 ms
5,376 KB |
testcase_16 | AC | 8 ms
5,376 KB |
testcase_17 | AC | 8 ms
5,376 KB |
testcase_18 | AC | 8 ms
5,376 KB |
testcase_19 | AC | 21 ms
6,268 KB |
testcase_20 | AC | 17 ms
6,016 KB |
testcase_21 | AC | 19 ms
6,436 KB |
testcase_22 | AC | 17 ms
6,012 KB |
testcase_23 | AC | 17 ms
5,376 KB |
testcase_24 | AC | 16 ms
7,840 KB |
testcase_25 | AC | 17 ms
7,892 KB |
testcase_26 | AC | 20 ms
7,708 KB |
testcase_27 | AC | 20 ms
7,960 KB |
testcase_28 | AC | 19 ms
7,832 KB |
testcase_29 | AC | 18 ms
7,960 KB |
testcase_30 | AC | 17 ms
7,988 KB |
testcase_31 | AC | 19 ms
7,960 KB |
testcase_32 | AC | 18 ms
7,840 KB |
testcase_33 | AC | 21 ms
7,964 KB |
testcase_34 | AC | 16 ms
7,840 KB |
testcase_35 | AC | 13 ms
7,968 KB |
testcase_36 | AC | 14 ms
7,928 KB |
testcase_37 | AC | 8 ms
5,632 KB |
testcase_38 | AC | 8 ms
5,632 KB |
testcase_39 | AC | 16 ms
5,892 KB |
testcase_40 | AC | 17 ms
5,764 KB |
testcase_41 | AC | 20 ms
5,888 KB |
testcase_42 | AC | 17 ms
5,756 KB |
testcase_43 | AC | 15 ms
5,632 KB |
testcase_44 | AC | 18 ms
7,876 KB |
testcase_45 | AC | 21 ms
7,964 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 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\floor-sum.hpp" #line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\floor-sum.hpp" #include <utility> namespace nachia{ // a : any value // mod != 0 std::pair<long long, unsigned long long> SafeDiv(long long a, unsigned long long mod){ using u64 = unsigned long long; if(a >= 0) return std::make_pair(0, (u64)a); if(mod >= (u64)1 << 62) return std::make_pair(-1, (u64)a + mod); long long q = a / mod; long long m = a % (long long)mod; if(m){ q--; m += mod; } return std::make_pair(q, m); } unsigned long long nC2Uint64(unsigned long long n){ return (n%2) ? ((n-1)/2*n) : (n/2*(n-1)); } // n : any // 1 <= m // a : any // b : any // n * a%m + b%m < 2**64 unsigned long long FloorSumU64Unsigned( unsigned long long n, unsigned long long m, unsigned long long a, unsigned long long b ){ using u64 = unsigned long long; assert(1 <= m); u64 ans = 0; while(n){ if(a >= m){ ans += a / m * nC2Uint64(n); a %= m; } if(b >= m){ ans += b / m * n; b %= m; } u64 y_max = a * n + b; if (y_max < m) return ans; n = y_max / m; b = y_max % m; y_max = a; a = m; m = y_max; } return ans; } // n : any // 1 <= m // a : any // b : any // (n+1) * m < 2**64 unsigned long long FloorSumU64Signed( unsigned long long n, unsigned long long m, long long a, long long b ){ using u64 = unsigned long long; auto ua = SafeDiv(a, m); auto ub = SafeDiv(b, m); u64 ans = FloorSumU64Unsigned(n, m, ua.second, ub.second); ans += ua.first / m * nC2Uint64(n); ans += ub.first / m * n; return ans; } } // namespace nachia #line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\rational-number-search.hpp" namespace nachia{ class RationalNumberSearch{ public: RationalNumberSearch(unsigned long long maxVal){ assert(maxVal < 1ull << 63); mx = maxVal; } bool hasNext(){ return state >= 0; } std::pair<unsigned long long, unsigned long long> getNext() const { switch(state){ case 0: return { a0+a1, b0+b1 }; case 1: return { a0+tr*a1, b0+tr*b1 }; case 2: return { a1+tr*a0, b1+tr*b0 }; case 3: return { a0+(tl+tr)/2*a1, b0+(tl+tr)/2*b1 }; case 4: return { a1+(tl+tr)/2*a0, b1+(tl+tr)/2*b0 }; } return {0,0}; } void give(bool toRight){ int x = toRight ? 1 : 0; switch(state){ case 0: tl = 1; tr = 2; if(a0 + a1 > mx || b0 + b1 > mx){ state = -1; } else{ state = (toRight ? 1 : 2); } break; case 1: case 2: if(x ^ (2-state)){ state += 2; } else{ tr *= 2; tl *= 2; } break; case 3: case 4: ((x ^ (4-state)) ? tr : tl) = (tl+tr)/2; break; } while(givecheck()); } private: using UInt = unsigned long long; UInt a0=0, b0=1, a1=1, b1=0, tl=0, tr=0, mx; int state = 0; bool givecheck(){ auto st = [this](int x){ state = x; return true; }; auto trq = [this](UInt x0, UInt x1) -> bool { bool f = x0+tr*x1 > mx; if(f) tr = (mx-x0)/x1 + 1; return f; }; bool f = false; switch(state){ case -1 : break; case 0: if(a0 + a1 > mx || b0 + b1 > mx){ state = -1; } break; case 1: if(trq(a0,a1)) f = true; if(trq(b0,b1)) f = true; if(f) return st(3); break; case 2: if(trq(a1,a0)) f = true; if(trq(b1,b0)) f = true; if(f) return st(4); break; case 3: if(tl + 1 == tr){ a0 += a1 * tl; b0 += b1 * tl; return st(0); } break; case 4: if(tl + 1 == tr){ a1 += a0 * tl; b1 += b0 * tl; return st(0); } break; } return false; } }; } // namespace nachia #line 5 "..\\Main.cpp" #include <string> #line 8 "..\\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>; i64 countFracs(i64 N){ vector<i64> cnt(N+1); for(i64 c=1; c<=N; c++) cnt[c] += c; nachia::DivisorMobius(cnt); i64 sumcnt = 0; for(int i=1; i<=N; i++) sumcnt += cnt[i]; return sumcnt; } pair<i64,i64> testcase(){ i64 N, K; cin >> N >> K; i64 cnt = countFracs(N); if(cnt * 2 - 1 < K) return {-1,-1}; if(cnt == K) return {1,1}; bool sw = false; if(cnt < K){ K = cnt*2 - K; sw = true; } vector<i64> quotients = {0}; for(i64 k=1; k*k<N; k++) quotients.push_back(k); int qp1 = quotients.size(); for(i64 k=1; k*k<=N; k++) quotients.push_back(N/k); reverse(quotients.begin() + qp1, quotients.end()); int numQ = quotients.size()-1; vector<i64> mobius(N+1); mobius[1] = 1; nachia::DivisorMobius(mobius); vector<i64> mertens = mobius; rep(i,N) mertens[i+1] += mertens[i]; auto srch = nachia::RationalNumberSearch(N); i64 a = 0, b = 0; i64 t = 0; while(srch.hasNext() && t < 100){ t++; i64 ax = srch.getNext().first; i64 bx = srch.getNext().second; i64 sumcnt = 0; rep(q,numQ){ i64 times = mertens[quotients[q+1]] - mertens[quotients[q]]; cnt = nachia::FloorSumU64Signed(quotients[numQ-q]+1, bx, ax, 0); sumcnt += times * cnt; } if(K <= sumcnt){ a = ax; b = bx; } srch.give(sumcnt < K); } if(sw) swap(a, b); 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;