UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#215155#2686. Oversleepingfddwd04337ms1260kbC++111.1kb2024-11-26 20:58:362024-11-26 23:04:57

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
ll x,y,p,q;
inline ll exgcd(ll a,ll b,ll &num3,ll &num4){
	if(!b){
		num3=1,num4=0;
		return a;
	}ll r=exgcd(b,a%b,num3,num4),tmp=num3;
	num3=num4,num4=tmp-a/b*num4;
	return r;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--){
		cin>>x>>y>>p>>q;
		ll ans=2e18,pos1=1,pos2=0;
		for(ll i=p;i<p+q;++i){
			const ll mod=2*(x+y);
			if(i%mod==0){ans=min(ans,i);break;}
			ll cl=((x-i)%mod+mod)%mod,ch=p+q;
			ll g=__gcd(cl,ch);cl/=g,ch/=g;
			if(__gcd(ch,mod)!=1) continue;
			exgcd(ch,mod,pos1,pos2);pos1=(pos1%mod+mod)%mod;
			(pos1*=cl)%=mod;
			ans=min(ans,i+pos1*(p+q));
		}for(ll i=x;i<x+y;++i){
			const ll mod=p+q;
			if(i%mod==0){ans=min(ans,i);break;}
			ll cl=((p-i)%mod+mod)%mod,ch=2*(x+y);
			ll g=__gcd(cl,ch);cl/=g,ch/=g;
			if(__gcd(ch,mod)!=1) continue;
			exgcd(ch,mod,pos1,pos2);pos1=(pos1%mod+mod)%mod;
			(pos1*=cl)%=mod;
			ans=min(ans,i+pos1*2*(x+y));
		}cout<<(ans==2e18?-1ll:ans)<<endl;
	}
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 1260kb

input:

10
42 337 468 315
179 261 297 332
336 189 230 33
240 398 38 204
465 158 454 462
112 184 90 263
320 4...

output:

758
297
493
240
465
112
475
187
386
268

result:

wrong answer 1st lines differ - expected: '1558', found: '758'

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 1260kb

input:

10
96 471 276 491
226 87 207 365
451 201 191 173
46 375 100 8
39 179 214 269
135 260 91 431
253 288 ...

output:

276
226
555
100
214
135
458
368
378
99

result:

wrong answer 8th lines differ - expected: '374', found: '368'

Test #3:

score: 0
Wrong Answer
time: 1ms
memory: 1256kb

input:

10
337 285 340 338
484 25 321 156
246 482 122 234
229 441 426 72
6 93 155 338
21 317 406 335
160 298...

output:

340
5574
246
426
198
676
372
469
437
492

result:

wrong answer 5th lines differ - expected: '204', found: '198'

Test #4:

score: 0
Wrong Answer
time: 2ms
memory: 1260kb

input:

10
196 433 313 366
262 415 94 30
353 22 242 460
283 172 13 276
56 247 344 4
297 363 415 479
473 26 6...

output:

313
342
353
283
4520
415
473
169
120
176

result:

wrong answer 5th lines differ - expected: '692', found: '4520'

Test #5:

score: 0
Wrong Answer
time: 0ms
memory: 1256kb

input:

10
437 267 140 198
383 155 226 424
273 308 151 317
15 231 435 285
404 294 253 64
109 199 388 147
425...

output:

478
383
273
492
570
923
427
467
328
123

result:

wrong answer 4th lines differ - expected: '507', found: '492'

Test #6:

score: 0
Wrong Answer
time: 0ms
memory: 1256kb

input:

10
21 426 135 234
111 51 109 11
185 42 230 22
472 346 269 285
77 128 499 461
173 79 230 382
102 127 ...

output:

135
111
4271
472
499
230
207
297
268
141

result:

wrong answer 3rd lines differ - expected: '2001', found: '4271'

Test #7:

score: 0
Wrong Answer
time: 6ms
memory: 1260kb

input:

10
790950658 153 395731486 328
228237805 89 805489534 371
733742769 407 150980036 116
210282811 256 ...

output:

2910819999953930
131670212810617
2052650203575473
481464741052336
2119094653165927
2195170223196727
...

result:

wrong answer 1st lines differ - expected: '493783472749894', found: '2910819999953930'

Test #8:

score: 0
Wrong Answer
time: 4ms
memory: 1260kb

input:

10
935151576 163 823994136 316
552819682 244 661178089 95
751586616 375 326537181 182
9424664 344 31...

output:

16016771198197604
7212423210651049
309929672717638
1902164539224
1034407235392958
58456733062296
468...

result:

wrong answer 1st lines differ - expected: '3487138752902582', found: '16016771198197604'

Test #9:

score: 0
Wrong Answer
time: 4ms
memory: 1256kb

input:

10
480628854 293 138727635 133
188840646 190 569211831 53
442713615 341 668626439 341
527553711 268 ...

output:

1302535268005995
4032666404768663
4334139081976695
28082225856120
10864583988810150
1282658979318908...

result:

wrong answer 1st lines differ - expected: '237399557723152', found: '1302535268005995'

Test #10:

score: 0
Wrong Answer
time: 4ms
memory: 1260kb

input:

10
128375946 395 45119743 26
591869966 93 644623523 312
553967887 448 714110036 391
129391856 52 673...

output:

173096624515978
4605051504620056
259872639599737
14331835905752
769601137168098
961565343460272
2389...

result:

wrong answer 5th lines differ - expected: '256533712389188', found: '769601137168098'

Test #11:

score: 0
Wrong Answer
time: 3ms
memory: 1256kb

input:

10
416394745 108 799849287 309
285823581 120 50495267 151
984269713 448 325585187 230
502469917 398 ...

output:

27057271341158295
1905880727155209
781934728273229
6221665323228427
4845873144235946
105521424453861...

result:

wrong answer 1st lines differ - expected: '510932724030159', found: '27057271341158295'

Test #12:

score: 0
Wrong Answer
time: 2ms
memory: 1260kb

input:

10
858503120 86 550141525 344
266071218 423 114926419 32
463189501 184 235629038 219
681438792 48 66...

output:

1864662953909472
203572210743994
108859302958239
8577276812029512
348331947701166
299409242240879
23...

result:

wrong answer 2nd lines differ - expected: '14279266757365', found: '203572210743994'

Test #13:

score: 0
Wrong Answer
time: 4ms
memory: 1260kb

input:

10
49615553 235 484012586 439
733063300 215 529603390 181
217670208 264 477723402 451
412727927 119 ...

output:

536778672945986
108602626683520
183965723103840
270657559821653
41968855301009741
11451740089500920
...

result:

wrong answer 1st lines differ - expected: '163825824623411', found: '536778672945986'

Test #14:

score: 0
Wrong Answer
time: 2ms
memory: 1256kb

input:

10
411060288 247 193494425 14
162692451 151 282497312 400
796796095 370 100991720 365
560074247 197 ...

output:

236839515269254
710816505468320
433677989580765
638082172634567
238702071887920
1014327193582686
145...

result:

wrong answer 2nd lines differ - expected: '56984873468971', found: '710816505468320'

Test #15:

score: 0
Wrong Answer
time: 555ms
memory: 1260kb

input:

10
733526255 46680 232614188 25143
740109721 35101 664765419 65813
926232187 19192 248710599 18813
7...

output:

483424517485
93633500986603
53004735144083
9067198590028
1006825631184
685064834622
84805986649153
1...

result:

wrong answer 2nd lines differ - expected: '2802928408299', found: '93633500986603'

Test #16:

score: 0
Wrong Answer
time: 654ms
memory: 1256kb

input:

10
40397805 9224 854461643 50758
463970290 6807 993317097 75888
496579182 67022 428873070 56575
8340...

output:

2384944063443
7726610589534
4885508641726
10990306568623
6103014773068
4510437960348
1709701068717
7...

result:

wrong answer 4th lines differ - expected: '3458814687913', found: '10990306568623'

Test #17:

score: 0
Wrong Answer
time: 624ms
memory: 1256kb

input:

10
677231818 45638 135553472 57886
334073954 74682 504512612 32658
528899984 14506 658263816 15374
1...

output:

12492382630282
7916315260794
186856497756164
1035101301992
4250858104139
6484554095599
1835106370808...

result:

wrong answer 1st lines differ - expected: '11785305009104', found: '12492382630282'

Test #18:

score: 0
Wrong Answer
time: 842ms
memory: 1256kb

input:

10
591761203 22205 53945697 65976
829627579 78277 112598137 27980
144133461 55044 668263637 96424
30...

output:

831455666035
2908118947003
291404913561
88666838913636
3950791693215
8266974861556
111818018746
7056...

result:

wrong answer 1st lines differ - expected: '408922312723', found: '831455666035'

Test #19:

score: 0
Wrong Answer
time: 881ms
memory: 1260kb

input:

10
798158737 58985 625637387 56023
950567276 86709 613154552 23440
2676550 96868 636525260 84971
205...

output:

830113703925077
69894932928656
23554542206
72816999418459
1962460002814
21055308702999
9071164247150...

result:

wrong answer 1st lines differ - expected: '1279542967427', found: '830113703925077'

Test #20:

score: 0
Wrong Answer
time: 749ms
memory: 1256kb

input:

10
76769987 47758 832950079 87350
226318103 39942 857729326 28604
700759579 85249 4088534 87174
7300...

output:

1867669828468
69239077838926
112835932059
63299765465801
118657188841543
9900452209294
730216990728
...

result:

wrong answer 1st lines differ - expected: '845532903085', found: '1867669828468'