提出 #62189079

---

ソースコード 拡げる

#include<bits/stdc++.h>
using std::cerr; using std::setw; using std::endl;
using std::cin; using std::cout;
template<typename Tp>
bool tomax(Tp &x,const Tp &y){if(x<y){x=y; return 1;} return 0;}
template<typename Tp>
bool tomin(Tp &x,const Tp &y){if(y<x){x=y; return 1;} return 0;}
using ll=long long; using ui=unsigned; using lf=double;
using ull=unsigned long long;
constexpr ll MAXV=2e12;
ll udiv(ll x,ll y){return (x+y-1)/y;}
ll getk(ll a,ll b,ll n,ll g){
    ll l=1,r=MAXV+1;
    while(l<r){
        ll mid=(l+r+1)>>1;
        if(mid-1-udiv(a*mid-g,b)>n) r=mid-1;
        else l=mid;
    }
    return r;
}
ll calc(ll a,ll m,ll L,ll R){
    if(L==0) return 0;
    if(a==0||L>R) return -1;
    ll t=udiv(L,a);
    if(a*t<=R) return t;
    ll k=calc(m%a,a,a-R%a,a-L%a);
    if(k==-1) return -1;
    return udiv(L+k*m,a);
}
void solve(){
    ll n,a,b; cin>>n>>a>>b;
    ll g=std::__gcd(a,b);
    ll k=getk(a,b,n,g);
    // cerr<<"k: "<<k<<endl;
    ll cntb=udiv(a*k-g,b),r=a*k-b*(cntb-1)-1;
    ll t;
    if(b-r-a>0){
        // ll rec=calc(a,b,b-r-a,b-1-a);
        // cerr<<"a,b: "<<a<<' '<<b
        //     <<"  l,r: "<<(b-r-a)<<' '<<(b-1-a)
        //     <<"  rec: "<<rec
        //     <<"  val: "<<(a*rec%b)
        //     <<endl;
        t=calc(a,b,b-r-a,b-1-a)+1;
    }else{
        t=1;
    }
    ll y=t*a,L=y+1,R=y+a*k-1;
    cout<<L<<' '<<R<<'\n';
    return ;
}
int main(){
    std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
    int T; cin>>T;
    for(int t=1;t<=T;t++){
        solve();
    }
    return 0;
}

提出情報

ジャッジ結果