結果

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

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=200005;
const ll inf=1e18;
const ll BASE=1000000000000000000;
struct BigInt{
    vector<ll> v;
    BigInt(ll n=0){if(n<0)return;v.push_back(n);norm();}
    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 o<*this;}
    bool operator<=(const BigInt&o)const{return not(o<*this);}
    bool operator>=(const BigInt&o)const{return not(*this<o);}
    bool operator==(const BigInt&o)const{return not(*this<o) and not(o<*this);}
    BigInt operator+(const BigInt&o)const{BigInt r;r.v.resize(max(v.size(),o.v.size()),0);ll c=0;for(int i=0;i<r.v.size() or c;i++){if(i==r.v.size())r.v.push_back(0);ll a=(i<v.size()?v[i]:0),b=(i<o.v.size()?o.v[i]:0);__int128 s=(__int128)a+b+c;r.v[i]=s%BASE;c=s/BASE;}return r;}
    BigInt operator-(const BigInt&o)const{BigInt r;r.v.resize(v.size());ll c=0;for(int i=0;i<v.size();i++){ll a=v[i],b=(i<o.v.size()?o.v[i]:0);__int128 s=(__int128)a-b-c;if(s<0){s+=BASE;c=1;}else c=0;r.v[i]=s;}r.norm();return r;}
    BigInt operator*(const BigInt&o)const{if(v.empty() or o.v.empty())return BigInt(0);BigInt r;r.v.resize(v.size()+o.v.size(),0);for(int i=0;i<v.size();i++){__int128 c=0;for(int j=0;j<o.v.size() or c;j++){__int128 s=r.v[i+j]+(__int128)v[i]*(j<o.v.size()?o.v[j]:0)+c;r.v[i+j]=s%BASE;c=s/BASE;}}r.norm();return r;}
    BigInt operator/(__int128 n)const{if(n==0)return BigInt(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]=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=v.size()-2;i>=0;i--)printf("%018lld",v[i]);printf("\n");}
};
ll D,A,B,K;
bool check(const BigInt& y){
    BigInt n1=y*BigInt(B)+BigInt(B-1),q1=n1/D;
    BigInt n2=y*BigInt(A),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--){
        scanf("%lld%lld%lld%lld",&D,&A,&B,&K);
        __int128 d=D,a=A,b=B;
        if(b*b<=a*d){
            __int128 req=(__int128)D*(K+1);
            if(req<B){BigInt ans((ll)req);ans.print();}
            else printf("-1\n");
        }else{
            BigInt l(0),r; r.v={0,0,500};
            BigInt ans; ans.v.clear();
            while(l<=r){
                BigInt mid=(l+r)/2;
                if(check(mid)){
                    ans=mid;
                    if(mid.v.size()==1 and mid.v[0]==0) break;
                    r=mid-BigInt(1);
                }else l=mid+BigInt(1);
            }
            if(ans.v.empty()) printf("-1\n");
            else{
                BigInt t1=ans*BigInt(B);
                BigInt t2=(ans*BigInt(A)/B+BigInt(K+1))*BigInt(D);
                if(t1<t2) t2.print(); else t1.print();
            }
        }
    }
    return 0;
}
0