#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 #include #include #include namespace nachia{ namespace prime_sieve_explicit_internal{ std::vector 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 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 SegmentedSieveExplicit(long long l, long long r){ assert(0 <= l); assert(l <= r); long long d = r - l; if(d == 0) return {}; std::vector 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 void DivisorZeta(std::vector& 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 void DivisorInvZeta(std::vector& 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 void DivisorMobius(std::vector& 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 void DivisorInvMobius(std::vector& 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 std::vector GcdConvolution(std::vector a, std::vector 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 std::vector LcmConvolution(std::vector a, std::vector 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 #line 7 "..\\Main.cpp" #include 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 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 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; } i64 l = 0, r = 1ll << 40; while(l+1 < r){ i64 m = (l+r)/2; vector cnt(N+1); for(i64 c=1; c<=N; c++){ i64 r = (m * c) >> 40; cnt[c] += r; } nachia::DivisorMobius(cnt); i64 sumcnt = 0; for(int i=1; i<=N; i++) sumcnt += cnt[i]; if(sumcnt < K) l = m; else r = m; } // l < x <= r if(l == (1ll << 40)) return {-1,-1}; i64 a = N+1, b = 1; for(int i=1; i<=N; i++){ i64 q = ((__int128_t)(l * i) >> 40) + 1; if(q > N) continue; if(q * b < a * i){ a = q; b = i; } } 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;