結果

問題 No.2066 Simple Math !
ユーザー 👑 NachiaNachia
提出日時 2022-09-02 23:19:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,480 bytes
コンパイル時間 893 ms
コンパイル使用メモリ 77,524 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-16 06:16:01
合計ジャッジ時間 5,456 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 187 ms
6,816 KB
testcase_10 AC 182 ms
6,820 KB
testcase_11 AC 188 ms
6,816 KB
testcase_12 AC 186 ms
6,820 KB
testcase_13 AC 186 ms
6,820 KB
testcase_14 AC 173 ms
6,820 KB
testcase_15 AC 172 ms
6,816 KB
testcase_16 AC 178 ms
6,816 KB
testcase_17 AC 177 ms
6,816 KB
testcase_18 AC 178 ms
6,816 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 93 ms
6,816 KB
testcase_25 AC 94 ms
6,820 KB
testcase_26 AC 93 ms
6,816 KB
testcase_27 AC 94 ms
6,816 KB
testcase_28 AC 92 ms
6,820 KB
testcase_29 AC 32 ms
6,820 KB
testcase_30 WA -
testcase_31 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "Main.cpp"

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#line 2 "nachia\\math\\floor-sum.hpp"

#include <cassert>
#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;
}


//
//  a i + b j < n  
//      ---+     
//       >         ( c i + d j + e )
//      ---+   
//    0 <= i, j
//
// - 0 <= n,a,b
template<class modint>
modint FloorSumTimesLinear(
    long long n,
    long long a,
    long long b,
    modint c,
    modint d,
    modint e
){
    if(n <= 0) return modint(0);
    if(a < b) return FloorSumTimesLinear(n, b, a, d, c, e);

    // eliminate triangle
    long long maxi = (n - 1) / a + 1;
    modint offset = 0;
    offset += c * modint(maxi) * modint(maxi-1) * modint(maxi+1) / modint(6);
    offset += d * modint(maxi) * modint(maxi-1) * modint(maxi+1) / modint(6);
    offset += e * modint(maxi) * modint(maxi+1) / modint(2);
    return offset + FloorSumTimesLinear(n-maxi*b, b, a-b, d, c-d, e+d*modint(maxi));
}

} // namespace nachia
#line 8 "Main.cpp"

using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(int)(n); i++)

u64 GCD(u64 a, u64 b){
    if(b == 0) return a;
    return GCD(b, a%b);
}

int main(){
    int T; cin >> T;
    rep(i,T){
        u64 P,Q,K; cin >> P >> Q >> K;
        u64 g = GCD(P,Q); P /= g; Q /= g;
        if(P > Q) swap(P,Q);
        u64 l = 0, r = P*Q+1;
        auto f = [&](u64 N) -> u64 {
            return nachia::FloorSumU64Unsigned(N/P+1, Q, P, N%P) + (N/P);
        };
        while(l + 1 < r){
            u64 N = (l+r)/2;
            if(f(N) < K) l = N; else r = N;
        }
        if(l == P*Q) r = P*Q + (K-f(P*Q));
        cout << r << '\n';
    }
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0