結果

問題 No.3398 Accuracy of Integer Division Approximate Function 2
コンテスト
ユーザー Mike scarf
提出日時 2025-12-12 15:44:57
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 3,434 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,168 ms
コンパイル使用メモリ 293,024 KB
実行使用メモリ 16,212 KB
最終ジャッジ日時 2025-12-12 15:45:04
合計ジャッジ時間 6,719 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1 TLE * 1 -- * 1
other -- * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:29:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   29 |     int t; scanf("%d",&t);
      |            ~~~~~^~~~~~~~~
main.cpp:31:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   31 |         ll d_in,a_in,b_in,k_in; scanf("%lld%lld%lld%lld",&d_in,&a_in,&b_in,&k_in);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=200005;
const __int128 BASE=1000000000000000000;
struct BigInt{
    vector<ll> v;
    BigInt(){v.clear();}
    BigInt(ll n){v.push_back(n); norm();}
    BigInt(__int128 n){while(n>0){v.push_back((ll)(n%BASE)); n/=BASE;} if(v.empty()) v.push_back(0);}
    void norm(){while(v.size()>1 and v.back()==0) v.pop_back();}
    bool operator<(const BigInt& o)const{if(v.size()!=o.v.size()) return v.size()<o.v.size(); for(int i=v.size()-1;i>=0;i--) if(v[i]!=o.v[i]) return v[i]<o.v[i]; return 0;}
    bool operator>=(const BigInt& o)const{return not(*this<o);}
    BigInt operator+(const BigInt& o)const{BigInt r; r.v.resize(max(v.size(),o.v.size()),0); __int128 c=0; for(size_t i=0;i<r.v.size() or c;i++){if(i==r.v.size()) r.v.push_back(0); __int128 val=c+(i<v.size()?v[i]:0)+(i<o.v.size()?o.v[i]:0); r.v[i]=(ll)(val%BASE); c=val/BASE;} return r;}
    BigInt operator-(const BigInt& o)const{BigInt r; r.v.resize(v.size()); __int128 c=0; for(size_t i=0;i<v.size();i++){__int128 val=(__int128)v[i]-(i<o.v.size()?o.v[i]:0)-c; if(val<0){val+=BASE; c=1;} else c=0; r.v[i]=(ll)val;} r.norm(); return r;}
    BigInt operator*(__int128 n)const{if(n==0) return BigInt((ll)0); BigInt r; r.v.resize(v.size()); __int128 c=0; for(size_t i=0;i<v.size() or c;i++){if(i==r.v.size()) r.v.push_back(0); __int128 val=c+(i<v.size()?(__int128)v[i]*n:0); r.v[i]=(ll)(val%BASE); c=val/BASE;} r.norm(); return r;}
    BigInt operator/(__int128 n)const{if(n==0) return BigInt((ll)0); BigInt r; r.v.resize(v.size()); __int128 c=0; for(int i=v.size()-1;i>=0;i--){__int128 val=c*BASE+v[i]; r.v[i]=(ll)(val/n); c=val%n;} r.norm(); return r;}
    void print(){if(v.empty()){printf("0\n"); return;} printf("%lld",v.back()); for(int i=(int)v.size()-2;i>=0;i--) printf("%018lld",v[i]); printf("\n");}
};
__int128 D,A,B,K,C;
bool check(BigInt y){
    BigInt n1=y*B+BigInt(B-1), q1=n1/D;
    BigInt n2=y*C, q2=n2/B;
    if(q1<q2) return 0;
    BigInt diff=q1-q2;
    return diff>=BigInt(K+1);
}
int main(){
    int t; scanf("%d",&t);
    while(t--){
        ll d_in,a_in,b_in,k_in; scanf("%lld%lld%lld%lld",&d_in,&a_in,&b_in,&k_in);
        D=d_in; A=a_in; B=b_in; K=k_in; C=(A*B)/D;
        __int128 lhs=B*B, rhs=D*C;
        BigInt ans((ll)-1);
        if(lhs<rhs){
            if(check(BigInt((ll)0))) ans=BigInt((ll)0);
        }else{
            BigInt low((ll)0), high; high.v={0,0,0,0,2}; 
            while(low<high or !(low<high or high<low)){
                BigInt mid=(low+high)/2;
                if(check(mid)) ans=mid, high=mid-BigInt((ll)1);
                else low=mid+BigInt((ll)1);
                if(high<low) break;
            }
        }
        if(ans.v.size()==1 and ans.v[0]==-1 and ans.v.back()==-1) printf("-1\n"); // Check if ans is -1
        else if(ans.v.size()==1 and ans.v[0]==-1) printf("-1\n"); // Handle BigInt(-1) stored as unsigned logic? No, BigInt is unsigned.
        // Wait, BigInt(-1) in my struct: v=[ -1 ]. But print expects positive.
        // Let's use a flag or check.
        // Actually, I initialized ans to -1 using (ll)-1. v becomes [-1].
        // So check if v.back() == -1.
        else{
            if(ans.v.size() && ans.v.back()==-1){ printf("-1\n"); continue; }
            BigInt r=(ans*C)/B+BigInt(K+1);
            BigInt x1=ans*B, x2=r*D;
            BigInt x=x1<x2?x2:x1;
            x.print();
        }
    }
    return 0;
}
0