QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#267186 | #5103. Fair Division | juampi | RE | 0ms | 0kb | Java8 | 2.6kb | 2023-11-27 01:05:43 | 2023-11-27 01:05:44 |
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);
int n = input.nextInt();
int m = input.nextInt();
// 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(int n, int 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: 0
Runtime Error
input:
13 382475111752106101