結果

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

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define u128 unsigned __int128
const ll maxn=200005;
const ll inf=1e18;
struct BI{
    vector<u128> v;
    BI(u128 x=0){ if(x)v.push_back(x); }
    void trim(){ while(v.size() and not v.back())v.pop_back(); }
    bool operator<(const BI& 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 false;
    }
    bool operator>(const BI& o)const{ return o<*this; }
    bool operator<=(const BI& o)const{ return not(*this>o); }
    bool operator>=(const BI& o)const{ return not(*this<o); }
    BI operator+(const BI& o)const{
        BI r; r.v.resize(max(v.size(),o.v.size()),0);
        u128 c=0;
        for(int i=0;i<r.v.size() or c;i++){
            if(i==r.v.size())r.v.push_back(0);
            u128 s=c+(i<v.size()?v[i]:0)+(i<o.v.size()?o.v[i]:0);
            r.v[i]=s%inf; c=s/inf;
        }
        return r;
    }
    BI operator-(const BI& o)const{
        BI r=*this; u128 b=0;
        for(int i=0;i<r.v.size();i++){
            u128 s=(i<o.v.size()?o.v[i]:0)+b;
            if(r.v[i]<s)r.v[i]+=inf-s,b=1; else r.v[i]-=s,b=0;
        }
        r.trim(); return r;
    }
    BI operator*(const BI& o)const{
        if(v.empty() or o.v.empty())return BI(0);
        BI r; r.v.resize(v.size()+o.v.size(),0);
        for(int i=0;i<v.size();i++){
            u128 c=0;
            for(int j=0;j<o.v.size() or c;j++){
                u128 s=r.v[i+j]+v[i]*(j<o.v.size()?o.v[j]:0)+c;
                r.v[i+j]=s%inf; c=s/inf;
            }
        }
        r.trim(); return r;
    }
    BI operator/(const BI& o)const{
        if(o.v.empty())return BI(0);
        BI q,cur; q.v.resize(v.size(),0);
        for(int i=v.size()-1;i>=0;i--){
            cur.v.insert(cur.v.begin(),v[i]); cur.trim();
            u128 l=0,r=inf-1,ans=0;
            while(l<=r){
                u128 mid=(l+r)/2;
                if(o*BI(mid)<=cur)ans=mid,l=mid+1; else r=mid-1;
            }
            q.v[i]=ans; cur=cur-(o*BI(ans));
        }
        q.trim(); return q;
    }
    void pr(){
        if(v.empty()){ printf("0"); return; }
        printf("%llu",(unsigned long long)v.back());
        for(int i=(int)v.size()-2;i>=0;i--)printf("%018llu",(unsigned long long)v[i]);
    }
};
u128 solve(u128 a,u128 b,u128 l,u128 r){
    if(l>r)return -1; if(not l)return 0; if(not a)return -1;
    u128 k=(l+a-1)/a;
    if(k*a<=r)return k;
    u128 sub=solve(b%a,a,(a-r%a)%a,(a-l%a)%a);
    if(sub==(u128)-1)return -1;
    return (sub*b+l+a-1)/a;
}
int main(){
    int t; scanf("%d",&t);
    while(t--){
        ll di,ai,bi,ki,v_val;
        u128 d,a,b,k,rm,ry,p,v_abs;
        BI q_final,k_st,p1,p2,kb,k1b,l_q,r_q,dk,num,mn,act,q,fl,t1,t2,df,x;
        bool v_neg=false,found=false;
        scanf("%lld%lld%lld%lld",&di,&ai,&bi,&ki);
        d=di,a=ai,b=bi,k=ki;
        rm=a%d; ry=(rm*b)/d; p=rm*b-d*ry;
        v_val=(ll)d*(ll)(k+1)-(ll)a+1;
        if(v_val<0) v_neg=true,v_abs=-v_val; else v_abs=v_val;
        if(v_val<=0){
            q_final=BI(0); found=true;
        } else if(rm==0){
        } else if(p==0){
            BI nm=BI(b)*BI(v_abs)+BI(d)-BI(1),dn(d),lm=nm/dn;
            if(lm<BI(b)){
                u128 lv=0; if(lm.v.size())lv=lm.v[0];
                u128 res=solve(ry,b,lv,b-1);
                if(res!=(u128)-1) q_final=BI(res),found=true;
            }
        } else {
            p1=BI(v_abs)*BI(ry); p2=BI(b)*BI(rm);
            if(not v_neg and p1>p2) k_st=(p1-p2)/BI(p); else k_st=BI(0);
            for(int i=0;i<2;i++){
                BI cur=k_st+BI(i);
                kb=cur*BI(b); k1b=(cur+BI(1))*BI(b);
                l_q=(kb+BI(ry)-BI(1))/BI(ry); r_q=(k1b+BI(ry)-BI(1))/BI(ry);
                dk=BI(d)*cur;
                if(v_neg){
                    if(dk>=BI(v_abs)) num=dk-BI(v_abs),mn=(num+BI(rm)-BI(1))/BI(rm);
                    else mn=BI(0);
                } else num=BI(v_abs)+dk,mn=(num+BI(rm)-BI(1))/BI(rm);
                act=l_q; if(mn>act)act=mn;
                if(act<r_q){ q_final=act; found=true; break; }
            }
        }
        if(not found) printf("-1\n");
        else {
            q=q_final; fl=(q*BI(ry))/BI(b);
            t1=(BI(k)+BI(1)+fl)*BI(d); t2=q*BI(rm);
            if(t1>t2) df=t1-t2; else df=BI(0);
            x=q*BI(a)+df; x.pr(); printf("\n");
        }
    }
    return 0;
}
0