QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#409956 | #8111. Coaches | Dinal | WA | 3ms | 3900kb | C++14 | 1.4kb | 2024-05-12 23:20:12 | 2024-05-12 23:20:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a,b;
ll solve(ll x,ll y,ll z,ll r);
ll evlos(ll x,ll y,ll z,ll r);
ll solve2(ll x,ll y,ll z,ll r){
ll X=x,Y=y;
x%=z,y%=z;
if(x>=r)return x;
if(!a)return LLONG_MAX;
x=z-1-x,y=z-y,r=z-1-r;
int kk=solve(x,y,z,r);
if(kk==-1)return LLONG_MAX;
return X+Y*kk;
}
void reimu_main(){
cin>>n>>a>>b;
ll l=a*b/__gcd(a,b);
ll ra=n%a,rb=n%b,rl=n%l;
ll sx=n/a+n/b-n/l*2;
ll sy=(min(ra,rb)<rl);
if(solve2(ra,a,b,rb)<rl)sy=2;
if(solve2(rb,b,a,ra)<rl)sy=2;
printf("%lld\n",n-sx+sy);
}
int main(){
int T;cin>>T;
while(T--)reimu_main();
return 0;
}
//ll solve(ll x,ll y,ll z,ll r){
// if(x<=r)return 0;
// if(!y)return -1;
// if(2*y>z)return evlos(z-1-x,z-y,z,z-1-r);
// ll k1=(z-x+y-1)/y,xx=(x+y*k1)%z;
// ll yy=(y-z%y)%y;
// ll cs=solve(xx,yy,y,r);
// if(cs==-1)return -1;
// ll res=(z+y-1)/y*cs+k1-(xx+cs*yy)/a;
// return res;
//}
ll solve(ll c,ll a,ll b,ll d){
if(c<=d)return 0;
if(a==0)return -1;
if(2*a>b)return evlos(b-1-c,b-a,b,b-1-d);
int k1=(b-c+a-1)/a,cc=(c+1ll*k1*a)%b;
int aa=(a-b%a)%a;
int cs=solve(cc,aa,a,d);
if(cs==-1)return -1;
int an=(b+a-1)/a*cs+k1-(cc+1ll*aa*cs)/a;
return an;
}
ll evlos(ll x,ll y,ll z,ll r){
if(x>=r)return 0;
if(!y)return -1;
ll k1=(r-x+y-1)/y,xx=x+y*k1;
if(xx<z)return k1;
ll cs=solve(xx-r,y,z,z-r-1);
if(cs==-1)return -1;
return cs+k1;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3780kb
input:
2 5 2 3 10 7 2
output:
3 6
result:
ok 2 number(s): "3 6"
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 3900kb
input:
1728 7 6 3 10 12 1 6 2 7 8 4 10 11 10 5 1 6 8 3 3 5 9 2 6 11 1 5 1 1 8 7 3 6 6 10 9 2 1 7 3 4 7 8 3 4 4 5 9 9 4 3 6 2 8 11 4 1 6 8 4 11 1 8 9 11 2 9 6 1 5 3 8 7 1 8 7 11 12 3 9 1 2 12 6 7 2 6 5 11 10 9 5 3 3 6 2 7 5 5 12 4 3 7 8 2 8 11 11 10 1 10 5 1 7 9 1 7 8 1 6 8 4 6 5 5 11 12 3 7 3 6 8 6 3 11 6 ...
output:
6 2 5 8 10 1 4 8 4 2 6 6 2 3 6 4 6 5 4 7 3 7 3 6 2 7 2 2 5 5 7 4 7 7 6 8 1 2 3 3 7 6 9 3 6 5 11 4 1 1 12 3 8 1 5 6 12 3 10 2 10 5 1 2 10 7 3 12 1 12 10 6 1 7 3 5 10 7 11 10 2 4 1 7 9 8 2 5 4 3 11 1 9 11 3 9 9 8 7 10 3 2 2 4 2 4 3 10 5 7 9 2 12 6 4 10 2 1 9 12 6 1 9 11 1 6 2 4 12 8 7 7 10 11 10 1 2 6...
result:
wrong answer 2nd numbers differ - expected: '1', found: '2'