QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#267183 | #5103. Fair Division | juampi | RE | 0ms | 0kb | Java11 | 1.8kb | 2023-11-27 00:59:00 | 2023-11-27 00:59:00 |
answer
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] tokens = in.nextLine().split(" ");
int n = Integer.parseInt(tokens[0]);
int m = Integer.parseInt(tokens[1]);
int p = -1;
int q = -1;
for (int qTest = 2; qTest <= 6000; qTest++) {
int term = (int) Math.pow(qTest, n - 1);
if (m < term) {
break;
}
term *= qTest;
boolean found = false;
for (int pTest = qTest - 1; pTest >= 0; pTest--) {
if (gcd(qTest, pTest) != 1) {
continue;
}
int sub = (int) Math.pow(pTest, n);
int div = term - sub;
int top = m * (qTest - pTest);
if (div > top) {
continue;
}
found = true;
if (top % div == 0) {
p = pTest;
q = qTest;
break;
}
}
if (found) {
break;
}
}
if (p == -1) {
System.out.println("impossible");
} else {
System.out.println(p + " " + q);
}
}
public static int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
public static long mypow(long b, int e) {
long res = 1;
long term = b;
while (e > 0) {
if ((e & 1) == 1) {
res = res * term;
}
e >>= 1;
term *= term;
}
return res;
}
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
13 382475111752106101