QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#308116 | #8111. Coaches | vme50 | ML | 175ms | 21060kb | C++17 | 1.1kb | 2024-01-19 16:07:26 | 2024-01-19 16:07:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define gcd __gcd
int T,a,b;ll n,d,t,ans;
void W(ll &x,ll y) {x=max(x,y);}
ll dv(ll x,ll y) {return x>0?(x-1)/y+1:0;}
int find1(int x,int r,int y,int p,int w1,int w2)
{
if(r<=y) return 0;if(x>=p) x-=p;
if(!x) return -1;int d=(p-r-1)/x,t;r+=(d+1)*x-p;
t=find1(x-p%x,r,y,x,(p-1)/x*w1+w2,((p-1)/x-1)*w1+w2);
return ~t?t+d*w1+w2:-1;
}
int find(int x,int r,int y,int p)
{x%=p;r%=p;return find1(p-x,p-r-1,p-y-1,p,1,1);}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%lld %d %d",&n,&a,&b);
ans=n-n/a-n/b;d=1ll*a/gcd(a,b)*b;
t=find(a,n%a,n%b,b);
if(~t) t=t*a+n%a,W(ans,n-n/a-n/b+dv(n-t,d)*2);
t=find(b,n%b,n%a,a);
if(~t) t=t*b+n%b,W(ans,n-n/a-n/b+dv(n-t,d)*2);
t=find(a,0,n%b,b);
if(~t) t*=a,W(ans,n-n/a-n/b+dv(n-t,d)*2-1);
t=find(b,0,n%a,a);
if(~t) t*=b,W(ans,n-n/a-n/b+dv(n-t,d)*2-1);
t=find(a,n%a,0,b);
if(~t) t=t*a+n%a,W(ans,n-n/a-n/b+dv(n-t,d)*2-1);
t=find(b,n%b,0,a);
if(~t) t=t*b+n%b,W(ans,n-n/a-n/b+dv(n-t,d)*2-1);
printf("%lld\n",ans);
}return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3792kb
input:
2 5 2 3 10 7 2
output:
3 6
result:
ok 2 number(s): "3 6"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3948kb
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 1 4 7 10 1 3 7 3 1 6 6 1 3 6 4 6 4 3 6 2 6 2 5 1 7 1 2 5 5 7 3 7 7 5 8 1 1 2 2 7 5 9 3 5 4 11 3 1 1 12 3 7 1 5 5 12 2 10 1 9 5 1 2 10 6 3 12 1 12 10 6 1 7 2 5 10 7 11 9 2 3 1 6 9 8 2 5 3 3 10 1 9 11 2 8 8 7 7 9 3 1 2 3 1 3 3 9 4 6 8 1 12 6 3 10 1 1 9 12 6 1 9 11 1 6 2 3 12 7 6 6 9 11 9 1 2 5 2 4 4...
result:
ok 1728 numbers
Test #3:
score: 0
Accepted
time: 26ms
memory: 3812kb
input:
97336 24 2 23 23 31 33 11 38 46 13 19 11 44 45 5 41 37 42 44 16 29 31 33 17 34 26 39 16 17 20 42 15 36 30 10 2 37 42 3 1 41 45 10 9 5 8 33 5 21 44 8 2 30 15 42 32 32 19 22 43 22 46 5 34 1 30 12 4 12 23 43 6 42 2 39 16 38 20 16 19 5 43 8 13 11 24 4 41 20 31 29 42 31 42 13 41 39 5 25 10 11 1 39 35 32 ...
output:
13 23 11 13 37 41 43 31 34 16 41 18 26 1 9 8 20 2 42 19 19 2 10 21 22 16 14 37 10 40 29 40 34 1 39 42 18 44 34 9 26 16 3 13 1 19 17 10 23 16 39 1 36 18 7 18 24 32 43 15 30 37 18 3 26 6 34 16 38 15 2 1 33 10 18 22 27 39 11 18 38 23 16 37 3 2 11 6 31 27 23 2 40 25 18 11 25 3 5 8 33 11 39 16 43 39 16 3...
result:
ok 97336 numbers
Test #4:
score: 0
Accepted
time: 74ms
memory: 18876kb
input:
100000 966978666727677953 103918709 172613701 10920141851516267 913419476 759905842 389768569272538945 536330283 640934149 639943523831961729 54166927 577019962 485205681543406081 198757 194331968 724016335198693249 813785681 961648601 939574367774573953 691820835 334275070 995545187588710401 304141...
output:
966978651820551992 10920141825190649 389768567937680831 639943510908627380 485203237846174806 724016333556113299 939574363605673886 995544858080726257 962654120619289539 812225197111279427 90146032962073878 73289302631177878 329554678347820923 761367689240413661 980502948980942906 937169598890548513...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 175ms
memory: 21060kb
input:
100000 1 381430977 960300601 686256692528718785 719055657 477193028 60578768596646331 46270321 87282398 402833229164491391 592176716 680258474 344840919482871306 254943231 676309228 11 500382582 783671905 122537283958788406 714103482 514787928 838360371006965443 314021286 889918835 1 719894397 38792...
output:
1 686256690136221421 60578766593355578 402833227892056205 344840917620366394 11 122537283549157942 838360367395145086 1 219954563067525991 998298806906957815 25 456255445850206934 20 681242361213592899 565821008805097290 106552742182169048 1 676030455668184427 930241736559223929 696661014588743445 1...
result:
ok 100000 numbers
Test #6:
score: -100
Memory Limit Exceeded
input:
100000 412694911046191617 109752726 4 611885622188585345 527624909 3 896125789270161921 8 99119385 336971263096778689 73023810 10 332408337631891137 3 272347821 690095136763649025 6 928269275 989053762600278401 3 641252028 624584537960286209 9 149144001 324081096302027777 65052370 7 2660893287906241...