結果
問題 | No.2262 Fractions |
ユーザー |
👑 ![]() |
提出日時 | 2023-04-08 11:18:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 77 ms / 2,000 ms |
コード長 | 10,712 bytes |
コンパイル時間 | 1,242 ms |
コンパイル使用メモリ | 94,800 KB |
最終ジャッジ日時 | 2025-02-12 03:49:11 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
#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 != 0std::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**64unsigned 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**64unsigned 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++;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;