結果
問題 | No.2066 Simple Math ! |
ユーザー |
|
提出日時 | 2022-09-02 22:36:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 482 ms / 2,000 ms |
コード長 | 2,756 bytes |
コンパイル時間 | 2,914 ms |
コンパイル使用メモリ | 180,148 KB |
最終ジャッジ日時 | 2025-02-07 01:35:11 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
#include <iostream>#include <vector>#include <string>#include <map>#include <set>#include <queue>#include <algorithm>#include <cmath>#include <iomanip>#include <random>#include <stdio.h>#include <fstream>#include <functional>#include <cassert>#include <unordered_map>#include <bitset>#include <atcoder/all>using namespace std;using namespace atcoder;#define rep(i,n) for (int i=0;i<n;i+=1)#define rrep(i,n) for (int i=n-1;i>-1;i--)#define pb push_back#define all(x) (x).begin(), (x).end()template<class T>using vec = vector<T>;template<class T>using vvec = vec<vec<T>>;template<class T>using vvvec = vec<vvec<T>>;using ll = long long;using pii = pair<int,int>;using pll = pair<ll,ll>;template<class T>bool chmin(T &a, T b){if (a>b){a = b;return true;}return false;}template<class T>bool chmax(T &a, T b){if (a<b){a = b;return true;}return false;}template<class T>T sum(vec<T> x){T res=0;for (auto e:x){res += e;}return res;}template<class T>ostream& operator<<(ostream& os, const vec<T>& A){os << "[";rep(i,A.size()){os << A[i];if (i!=A.size()-1){os << ' ';}}os<<"]";return os;}template<class T>ostream& operator<<(ostream& os, const set<T>& A){os << "{";for (auto e:A){os << e;auto it = A.find(e);it++;if (it!=A.end()){os << " ";}}os << "}";return os;}template<class T,class U>ostream& operator<<(ostream& os, const pair<T,U>& A){os << "(" << A.first <<", " << A.second << ")";return os;}template<class T>ostream& operator<<(ostream& os, const deque<T>& A){os << "deque({";rep(i,A.size()){os << A[i];if (i!=A.size()-1){os << ' ';}}os<<"})";return os;}ll solve(){ll P,Q,K;cin>>P>>Q>>K;ll g = gcd(P,Q);ll p = P/g, q = Q/g;auto [r0,m0] = crt({1,0},{p,q});ll x0 = (1-r0)/p, y0 = r0/q;if (0 <= x0){return K * g;}x0 *= -1;ll PQ_less = 0;auto cnt = [&](ll m){if (m < p*q){ll tmp = 0;tmp += floor_sum(p,p,y0,y0) * (m/p) + (m/p) * (m/p-1)/2 * y0 * p + floor_sum(m%p,p,y0,y0) + (m/p) * y0 * (m%p);tmp -= floor_sum(q,q,x0,x0-1) * (m/q) + (m/q) * (m/q-1)/2 * x0 * q + floor_sum(m%q,q,x0,x0-1) + (m/q) * x0 * (m%q);return tmp;}else{return PQ_less + m-p*q+1;}};PQ_less = cnt(p*q-1);ll ok = 1e18;ll ng = 0;while (ok-ng>1){ll mid = (ok+ng)/2;if (cnt(mid) >= K){ok = mid;}else{ng = mid;}}return ok * g;}int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);int T;cin>>T;while (T--){cout << solve() << endl;}}