TopCoder Statistics - Problem Statement

Problem Statement

Arpa took part in an exam called Konkoor. Here is one of questions that was on the exam:

You are given positive integers d and s. Find nonnegative integers a and b such that gcd(a, b) = d and a^2 - b^2 = s.

Given the longs d and s, compute and return the largest possible value of a. If there is no solution, return -1 instead.

Definition

Class:: ArpaKonkoori
Method:: getA
Parameters:: long, long
Returns:: long
Method signature:: long getA(long d, long s)
(be sure your method is public)

Constraints

d will be between 1 and 10^12, inclusive.
s will be between 1 and 10^12, inclusive.

Examples

5

2975

Returns: 300

There are two valid pairs (a, b): (300, 295) and (60, 25). Thus, the largest possible value of a is 300.
1

2975

Returns: 1488

This time there are four solutions. The one with the largest value a is a=1488, b=1487.
1

1000000000000

Returns: 250000000001
64

1000000000000

Returns: 7812500032
5

1000000000000

Returns: 50000000005
32

188956800000

Returns: 2952450016
96

188956800000

Returns: 984150048
1

188956800000

Returns: 47239200001
1

100

Returns: -1

There is no valid solution. There are some pairs (a, b) such that a^2 - b^2 = 100. However, none of them have gcd(a, b) = 1.
1

10000

Returns: 2501
12345678901

345

Returns: -1
3

9

Returns: 3

The only solution here is a=3, b=0.
70230644898

607438024591

Returns: -1
629013726734

280648065557

Returns: -1
423107726802

675995276784

Returns: -1
872054062689

723352089582

Returns: -1
440044527

871730498632

Returns: -1
796637203186

10937940716

Returns: -1
897293416772

347457435530

Returns: -1
470589122163

258686081905

Returns: -1
564888141584

486873550372

Returns: -1
266106568450

614323191592

Returns: -1
787586051200

389500281984

Returns: -1
376243325326

633755884201

Returns: -1
218020693183

864313288104

Returns: -1
802474369169

137590475323

Returns: -1
108808392515

637213539851

Returns: -1
559993206405

895673031139

Returns: -1
104165131106

960564318198

Returns: -1
252892449072

768485673033

Returns: -1
368704154405

516334757417

Returns: -1
123455308679

458586863890

Returns: -1
894486

800105204196

Returns: 894486
194

450767463444

Returns: 1161771910
141586

621444457276

Returns: 2265376
916

457932432176

Returns: 249963576
94494

696471050808

Returns: -1
11

197413617016

Returns: 4486673125
332

820857747872

Returns: -1
1

689544082806

Returns: -1
4

568018009856

Returns: 35501125620
1000000

1000000000000

Returns: 1000000
2183

759280596881

Returns: 173908695
497

947369673285

Returns: 953088451
1069

691308695906

Returns: -1
182

384524525112

Returns: -1
11206

181831783328

Returns: 4067778
45788

138371702304

Returns: -1
10

674147190900

Returns: 33707359550
116963

191524807166

Returns: -1
483

884398599

Returns: 915768
14

56540008280

Returns: -1
1

150502977886

Returns: -1
63

214307623530

Returns: -1
62494

23433000216

Returns: -1
5

304488799475

Returns: 30448879950
219766

96594189512

Returns: -1
770180

593177232400

Returns: 770180
5104

37929988096

Returns: 1862960
6

393946447644

Returns: 32828870640
166

505142758888

Returns: -1
608911

741545211842

Returns: -1
1130

153434857800

Returns: -1
15034

655009310088

Returns: -1
1012

641823875792

Returns: 317107164
18

706743731412

Returns: 19631770326
15

17276489550

Returns: -1
296847

440590707045

Returns: 890541
40247

408194894268

Returns: -1
3404

253516698864

Returns: 37239760
17124

706101153408

Returns: 10325772
15

908093176200

Returns: 15134886285
268

675043322624

Returns: 629704860
100

54876510000

Returns: 274382600
503

407184841321

Returns: 404756555
4

610173808224

Returns: -1
512396

787648982448

Returns: 1024792
3324

596810438640

Returns: 89774592
75

155042566875

Returns: 1033617150
105512

578904671488

Returns: -1
1761

176897245203

Returns: 50227242
7

75874612422

Returns: -1
2279

533532122884

Returns: -1
386

263236001072

Returns: -1
726

513993446604

Returns: 353990340
967

863737033855

Returns: 446607016
1136

210118558720

Returns: -1
513644

263830158736

Returns: 513644
1

506231356623

Returns: 253115678312
122929

498680788353

Returns: 2089793
616

482360293184

Returns: 391526520
10

611211509800

Returns: -1
60686

445617662116

Returns: 3701846
100021

410172218081

Returns: 2100441
137118

733252491036

Returns: 2742360
7879

627552981869

Returns: 39828345
178126

698035181272

Returns: -1
4446

235305368064

Returns: 13235742
714564

510601710096

Returns: 714564
59704

110501596096

Returns: 955264
246

178600326156

Returns: 363008916
941509

886439197081

Returns: 941509
670134

449079577956

Returns: 670134
233075

54323955625

Returns: 233075
8186

814513794380

Returns: 49754508
28613

205494646019

Returns: 3605238
118028

195028522976

Returns: -1
7

340363628402

Returns: -1
63950

462125082500

Returns: 3645150
622565

775174358450

Returns: -1
108448

658614247424

Returns: 1626720
104

576494087104

Returns: 2771606240
1

1

Returns: 1
1

2

Returns: -1
2

1

Returns: -1
2

2

Returns: -1
2

4

Returns: 2
1

100000000000

Returns: 25000000001
100000000000

100000000000

Returns: -1
1

999999999999

Returns: 500000000000
1

8

Returns: 3
30064771073

60129542145

Returns: -1

Statistics

Problem Statement for "ArpaKonkoori"

Problem Statement

Definition

Constraints

Examples