QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#267188 | #5103. Fair Division | juampi | WA | 67ms | 39524kb | Java8 | 2.6kb | 2023-11-27 01:07:15 | 2023-11-27 01:07:15 |
Judging History
answer
import java.util.Scanner;
public class FairDivision {
// Just calculates b to the e power...a speed up.
public static long mypow(long b, long e) {
long res = 1;
long term = b;
while (e > 0) {
if ((e & 1) == 1) {
res = res * term;
}
e >>= 1;
term *= term;
}
return res;
}
// GCD...maybe I should just call the built-in one =)
public static long gcd(long a, long b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
// Main function.
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
long n = input.nextLong();
long m = input.nextLong();
// Solve it.
long p, q;
long[] res = go(n, m);
p = res[0];
q = res[1];
// Here is what they ask us to output.
if (p == -1) {
System.out.println("impossible");
} else {
System.out.println(p + " " + q);
}
input.close();
}
// Solve it!
public static long[] go(long n, long m) {
// The fraction just doesn't work...
if (n > 70) {
return new long[]{-1, -1};
}
// I guessed, but I think about 3000 is the upper bound because there
// are at least 6 pirates...
for (int q = 2; q < 6000; q++) {
// We are trying q first and we need this value.
long term = mypow(q, n - 1);
if (m < term) {
break;
}
// We are okay to try it, so multiply by q.
term *= q;
boolean found = false;
// Try p...
for (int p = q - 1; p > 0; p--) {
// Not allowed.
if (gcd(q, p) != 1) {
continue;
}
// Calculate the desired fraction.
long sub = mypow(p, n);
long div = term - sub;
long top = m * (q - p);
// Has to be an integer...
if (div > top) {
continue;
}
found = true;
// This is our criteria for a solution.
if (top % div == 0) {
return new long[]{q - p, q};
}
}
if (!found) {
break;
}
}
// If we get here, no p, q worked...
return new long[]{-1, -1};
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 66ms
memory: 38508kb
input:
13 382475111752106101
output:
17 28
result:
ok single line: '17 28'
Test #2:
score: 0
Accepted
time: 50ms
memory: 39388kb
input:
59 576460752303423487
output:
1 2
result:
ok single line: '1 2'
Test #3:
score: 0
Accepted
time: 67ms
memory: 38724kb
input:
15 227368755046033249
output:
13 14
result:
ok single line: '13 14'
Test #4:
score: 0
Accepted
time: 54ms
memory: 37924kb
input:
27 72027091647987988
output:
1 4
result:
ok single line: '1 4'
Test #5:
score: 0
Accepted
time: 60ms
memory: 38828kb
input:
12 817283057828223168
output:
10 17
result:
ok single line: '10 17'
Test #6:
score: 0
Accepted
time: 45ms
memory: 38456kb
input:
40 279103330129289325
output:
1 2
result:
ok single line: '1 2'
Test #7:
score: 0
Accepted
time: 54ms
memory: 37956kb
input:
9 200754090585004509
output:
27 31
result:
ok single line: '27 31'
Test #8:
score: 0
Accepted
time: 50ms
memory: 39364kb
input:
13 145272043713167318
output:
11 19
result:
ok single line: '11 19'
Test #9:
score: 0
Accepted
time: 54ms
memory: 39524kb
input:
13 330339892079732537
output:
3 5
result:
ok single line: '3 5'
Test #10:
score: -100
Wrong Answer
time: 60ms
memory: 37860kb
input:
8 518312274023062851
output:
255 256
result:
wrong answer 1st lines differ - expected: '35 81', found: '255 256'