UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#215170#2686. OversleepingThySecret70270ms1160kbC++111.8kb2024-11-26 21:55:552024-11-26 23:06:30

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long
// #define x first
// #define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

inline void debug() { cerr << '\n'; }
template<typename Type, typename... Other>
inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }
#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a);

typedef long long LL;
typedef pair<int, int> PII;

const int N = 200010;
const int INF = 2e18;

template<typename Type>
inline void read(Type &res)
{
    res = 0;
    int ch = getchar(), flag = 0;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    res = flag ? -res : res;
}
template<typename Type, typename... Other>
inline void read(Type &res, Other&... y) { read(res), read(y...); }

int X, Y, P, Q, ans;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int exgcd(int a, int b, int &x, int &y)
{
	if (b == 0)
	{
		x = 1, y = 0;
		return a;
	}
	int d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

void solve()
{
    ans = INF;
    read(X, Y, P, Q);

    int a = 0, b = 0;
    int gcd = exgcd(2 * (X + Y), P + Q, a, b);

    for (int i = 0; i < Y; i ++)    // i stands for n
    {
        for (int j = 0; j < Q; j ++)    // j stands for m
        {
            if ((P + j - (i + X)) % gcd != 0) continue;
            int base = (P + j - (X + i)) / gcd, fc = (P + Q) / gcd;
            int ansx = a * base, ansy = b * base;

            ansx = (ansx % fc + fc) % fc;
            ans = min(ans, 2 * (X + Y) * ansx + X + i);
        }
    }
    cout << (ans == INF ? -1 : ans) << '\n';
}

signed main()
{
    int T; read(T);
    while (T --) solve();
    return 0;
}   

Details

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

Test #1:

score: 5
Accepted
time: 16ms
memory: 1156kb

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:

1558
297
493
240
465
112
475
187
386
268

result:

ok 10 lines

Test #2:

score: 5
Accepted
time: 21ms
memory: 1160kb

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
374
378
99

result:

ok 10 lines

Test #3:

score: 5
Accepted
time: 16ms
memory: 1160kb

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
204
697
372
469
437
492

result:

ok 10 lines

Test #4:

score: 5
Accepted
time: 17ms
memory: 1160kb

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
692
415
473
169
131
176

result:

ok 10 lines

Test #5:

score: 5
Accepted
time: 13ms
memory: 1156kb

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
507
570
923
427
467
328
123

result:

ok 10 lines

Test #6:

score: 5
Accepted
time: 9ms
memory: 1160kb

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
2001
472
499
230
207
297
268
141

result:

ok 10 lines

Test #7:

score: 5
Accepted
time: 29ms
memory: 1156kb

input:

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

output:

493783472749894
131670212810617
330447842999852
481464741052336
2119094653165927
381754206652115
142...

result:

ok 10 lines

Test #8:

score: 5
Accepted
time: 22ms
memory: 1156kb

input:

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

output:

3487138752902582
952405355171833
309929672717638
1902164539224
1034407235392958
58456733062296
46884...

result:

ok 10 lines

Test #9:

score: 5
Accepted
time: 23ms
memory: 1160kb

input:

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

output:

237399557723152
178379620207918
624787596542179
28082225856120
154525454225454
13205465448836
439872...

result:

ok 10 lines

Test #10:

score: 5
Accepted
time: 18ms
memory: 1160kb

input:

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

output:

173096624515978
4605051504620056
259872639599737
14331835905752
256533712389188
961565343460272
2285...

result:

ok 10 lines

Test #11:

score: 5
Accepted
time: 17ms
memory: 1160kb

input:

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

output:

510932724030159
43176814096641
781934728273229
826594318863817
605989098384493
1055214244538613
4068...

result:

ok 10 lines

Test #12:

score: 5
Accepted
time: 22ms
memory: 1160kb

input:

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

output:

1864662953909472
14279266757365
108859302958239
1097058610098552
348331947701166
299409242240879
193...

result:

ok 10 lines

Test #13:

score: 5
Accepted
time: 26ms
memory: 1160kb

input:

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

output:

163825824623411
108602626683520
183965723103840
270657559821653
638700923672972
401939204684136
6208...

result:

ok 10 lines

Test #14:

score: 5
Accepted
time: 21ms
memory: 1160kb

input:

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

output:

236839515269254
56984873468971
140848914321215
638082172634567
238702071887920
451994876108778
14552...

result:

ok 10 lines

Test #15:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Test #16:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Test #17:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Test #18:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Test #19:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Test #20:

score: 0
Time Limit Exceeded

input:

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

output:


result: