QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#308116#8111. Coachesvme50ML 175ms21060kbC++171.1kb2024-01-19 16:07:262024-01-19 16:07:26

Judging History

你现在查看的是最新测评结果

  • [2024-01-19 16:07:26]
  • 评测
  • 测评结果:ML
  • 用时:175ms
  • 内存:21060kb
  • [2024-01-19 16:07:26]
  • 提交

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...

output:


result: