結果
| 問題 | No.3398 Accuracy of Integer Division Approximate Function 2 |
| コンテスト | |
| ユーザー |
 Mike scarf
|
| 提出日時 | 2025-12-12 15:40:31 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 5,305 bytes |
| 記録 | |
| コンパイル時間 | 3,678 ms |
| コンパイル使用メモリ | 299,584 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2025-12-12 15:40:37 |
| 合計ジャッジ時間 | 5,864 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 2 RE * 1 |
| other | WA * 15 RE * 5 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:104:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
104 | int t; scanf("%d",&t);
| ~~~~~^~~~~~~~~
main.cpp:106:41: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
106 | ll D_in, A_in, B_in, K_in; scanf("%lld%lld%lld%lld",&D_in,&A_in,&B_in,&K_in);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=200005;
const __int128 B=1000000000000000000;
struct BigInt{
vector<ll> v; bool sgn;
BigInt(){v.clear(); sgn=0;}
BigInt(long long n){if(n<0) sgn=1,n=-n; else sgn=0; if(n==0) v.push_back(0); while(n>0){v.push_back(n%B); n/=B;}}
BigInt(__int128 n){if(n<0) sgn=1,n=-n; else sgn=0; if(n==0) v.push_back(0); while(n>0){v.push_back((ll)(n%B)); n/=B;}}
bool operator<(const BigInt& o)const{if(sgn!=o.sgn) return sgn; if(v.size()!=o.v.size()) return sgn?(v.size()>o.v.size()):(v.size()<o.v.size()); for(int i=v.size()-1;i>=0;i--) if(v[i]!=o.v[i]) return sgn?(v[i]>o.v[i]):(v[i]<o.v[i]); return 0;}
bool operator>(const BigInt& o)const{return o<*this;}
bool operator<=(const BigInt& o)const{return not(*this>o);}
bool operator>=(const BigInt& o)const{return not(*this<o);}
bool operator==(const BigInt& o)const{return sgn==o.sgn and v==o.v;}
BigInt operator+(const BigInt& o)const{
BigInt r; r.sgn=sgn;
if(sgn==o.sgn){
__int128 c=0;
for(size_t i=0;i<max(v.size(),o.v.size()) or c;i++){
__int128 val=c+(i<v.size()?v[i]:0)+(i<o.v.size()?o.v[i]:0);
r.v.push_back((ll)(val%B)); c=val/B;
}
}else{
if((*this).abs()<o.abs()){r=o+(*this); return r;}
__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+=B; c=1;} else c=0;
r.v.push_back((ll)val);
}
while(r.v.size()>1 and r.v.back()==0) r.v.pop_back();
if(r.v.size()==1 and r.v[0]==0) r.sgn=0;
}
return r;
}
BigInt operator-(const BigInt& o)const{BigInt t=o; t.sgn=not t.sgn; return *this+t;}
BigInt operator*(__int128 n)const{
BigInt r; if(n==0){r.v.push_back(0); return r;}
r.sgn=sgn^(n<0); n=n<0?-n:n; __int128 c=0;
for(size_t i=0;i<v.size() or c;i++){
__int128 val=c+(i<v.size()?(__int128)v[i]*n:0);
r.v.push_back((ll)(val%B)); c=val/B;
}
return r;
}
BigInt abs()const{BigInt r=*this; r.sgn=0; return r;}
void print(){if(sgn and not(v.size()==1 and v[0]==0)) printf("-"); printf("%lld",v.back()); for(int i=(int)v.size()-2;i>=0;i--) printf("%018lld",v[i]); printf("\n");}
};
BigInt operator*(__int128 n, const BigInt& b){return b*n;}
BigInt div_floor(BigInt a, __int128 b){
BigInt q; __int128 r=0; bool qs=a.sgn^(b<0); b=b<0?-b:b;
for(int i=(int)a.v.size()-1;i>=0;i--){
__int128 val=r*B+a.v[i];
if(q.v.size() or val/b) q.v.push_back((ll)(val/b));
r=val%b;
}
reverse(q.v.begin(),q.v.end());
if(q.v.empty()) q.v.push_back(0);
q.sgn=qs;
if(q.v.size()==1 and q.v[0]==0) q.sgn=0;
if(a.sgn and r!=0) return q-BigInt((ll)1);
return q;
}
BigInt max_bi(BigInt a, BigInt b){return a<b?b:a;}
BigInt solve1(__int128 a, BigInt b, __int128 c, __int128 d, BigInt e, __int128 f, BigInt k, BigInt L);
BigInt solve2(__int128 a, __int128 b, BigInt c, __int128 d, __int128 e, BigInt k, BigInt L){
if(a==0){
BigInt rhs=div_floor(k*(-1),e);
if(L<rhs or L==rhs) return L;
return BigInt((ll)-1);
}
BigInt t1=div_floor(L*b+c,d), t2=div_floor(L*e+k+BigInt(a-1),a);
BigInt y_min=max_bi(t1,t2);
BigInt Y=solve1(a,k*(-1),e,d,c*(-1)+BigInt(b-1),b,BigInt((ll)0),y_min);
if(Y.sgn and Y.v.back()==1 and Y.v.size()==1) return BigInt((ll)-1);
return max_bi(L,div_floor(Y*d-c+BigInt(b-1),b));
}
BigInt solve1(__int128 a, BigInt b, __int128 c, __int128 d, BigInt e, __int128 f, BigInt k, BigInt L){
if(L.sgn) L=BigInt((ll)0);
if(div_floor(L*a+b,c)-div_floor(L*d+e,f)>=k) return L;
__int128 q1=a/c, r1=a%c, q2=d/f, r2=d%f, alpha=q1-q2;
if(alpha>0){
BigInt cur=div_floor(L*a+b,c)-div_floor(L*d+e,f);
BigInt add=div_floor(k-cur+BigInt(alpha-1),alpha)+BigInt((ll)2);
BigInt low=L, high=L+add, mid, ans=BigInt((ll)-1);
while(low<high or low==high){
mid=div_floor(low+high,2);
if(mid<L) {low=L; continue;}
if(div_floor(mid*a+b,c)-div_floor(mid*d+e,f)>=k) ans=mid, high=mid-BigInt((ll)1);
else low=mid+BigInt((ll)1);
if(low>high) break;
}
return ans;
}else if(alpha<0) return BigInt((ll)-1);
else{
BigInt u_min=div_floor(L*r2+e,f);
BigInt res=solve2(r2,c,k*c-b+BigInt(r1-1),r1,f,e*(-1),u_min);
if(res.sgn and res.v.back()==1 and res.v.size()==1) return BigInt((ll)-1);
return max_bi(L,div_floor((res+k)*c-b+BigInt(r1-1),r1));
}
}
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);
__int128 D=D_in, A=A_in, B_val=B_in, K=K_in;
__int128 C=(A*B_val)/D;
BigInt q=solve1(A,BigInt(A-1),D,C,BigInt((ll)0),B_val,BigInt(K+1),BigInt((ll)0));
if(q.sgn and q.v.back()==1 and q.v.size()==1) printf("-1\n");
else{
BigInt rhs=div_floor(q*C,B_val)+BigInt(K+1);
BigInt r_min=rhs*D-q*A;
if(r_min.sgn) r_min=BigInt((ll)0);
(q*A+r_min).print();
}
}
return 0;
}