QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#267200#5103. Fair DivisionjuampiTL 105ms51808kbJava82.8kb2023-11-27 01:45:052023-11-27 01:45:06

Judging History

你现在查看的是最新测评结果

  • [2023-11-27 01:45:06]
  • 评测
  • 测评结果:TL
  • 用时:105ms
  • 内存:51808kb
  • [2023-11-27 01:45:05]
  • 提交

answer

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static long pow2(long a, long b) {
        long re = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                re *= a;        
            }
            b >>= 1;
            a *= a; 
        }
        return re;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNext()) {
            try {
                long N = scanner.nextLong();
                long M = scanner.nextLong();

                if (N > 200) N = 200;

                int p, q;
                double[] pw = new double[2];
                for (q = 2; ; q++) {
                    pw = pushBack(pw, pow2(q, N));
                    for (p = 1; p < q; p++) {
                        double d = pw[q] - pw[q - p];
                        if (d > 1.1 * M * q) {
                            if (p == 1) {
                                throw new ImpossibleException("impossible");
                            }
                            continue;
                        }
                        BigInteger qp = BigInteger.ONE;
                        BigInteger pp = BigInteger.ONE;
                        for (int i = 0; i < N; i++) {
                            qp = qp.multiply(BigInteger.valueOf(q));
                        }
                        for (int i = 0; i < N; i++) {
                            pp = pp.multiply(BigInteger.valueOf(q - p));
                        }
                        if (BigInteger.valueOf(M).multiply(BigInteger.valueOf(p)).mod(qp.subtract(pp)).equals(BigInteger.ZERO)) {
                            throw new FoundSolutionException(p, q);
                        }
                    }
                }
            } catch (ImpossibleException e) {
                System.out.println(e.getMessage());
            } catch (FoundSolutionException e) {
                done(e.getP(), e.getQ());
            }
        }
    }

    private static double[] pushBack(double[] array, double value) {
        double[] newArray = new double[array.length + 1];
        System.arraycopy(array, 0, newArray, 0, array.length);
        newArray[array.length] = value;
        return newArray;
    }

    private static void done(int p, int q) {
        System.out.println(p + " " + q);
    }
}

class ImpossibleException extends Exception {
    public ImpossibleException(String message) {
        super(message);
    }
}

class FoundSolutionException extends Exception {
    private final int p;
    private final int q;

    public FoundSolutionException(int p, int q) {
        this.p = p;
        this.q = q;
    }

    public int getP() {
        return p;
    }

    public int getQ() {
        return q;
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 71ms
memory: 42184kb

input:

13 382475111752106101

output:

17 28

result:

ok single line: '17 28'

Test #2:

score: 0
Accepted
time: 52ms
memory: 38816kb

input:

59 576460752303423487

output:

1 2

result:

ok single line: '1 2'

Test #3:

score: 0
Accepted
time: 52ms
memory: 39784kb

input:

15 227368755046033249

output:

13 14

result:

ok single line: '13 14'

Test #4:

score: 0
Accepted
time: 60ms
memory: 38388kb

input:

27 72027091647987988

output:

1 4

result:

ok single line: '1 4'

Test #5:

score: 0
Accepted
time: 61ms
memory: 39556kb

input:

12 817283057828223168

output:

10 17

result:

ok single line: '10 17'

Test #6:

score: 0
Accepted
time: 53ms
memory: 38668kb

input:

40 279103330129289325

output:

1 2

result:

ok single line: '1 2'

Test #7:

score: 0
Accepted
time: 67ms
memory: 41680kb

input:

9 200754090585004509

output:

27 31

result:

ok single line: '27 31'

Test #8:

score: 0
Accepted
time: 74ms
memory: 38712kb

input:

13 145272043713167318

output:

11 19

result:

ok single line: '11 19'

Test #9:

score: 0
Accepted
time: 50ms
memory: 40152kb

input:

13 330339892079732537

output:

3 5

result:

ok single line: '3 5'

Test #10:

score: 0
Accepted
time: 105ms
memory: 49332kb

input:

8 518312274023062851

output:

35 81

result:

ok single line: '35 81'

Test #11:

score: 0
Accepted
time: 62ms
memory: 41656kb

input:

8 226575677743060500

output:

3 37

result:

ok single line: '3 37'

Test #12:

score: 0
Accepted
time: 50ms
memory: 38816kb

input:

22 947676267664323372

output:

5 6

result:

ok single line: '5 6'

Test #13:

score: 0
Accepted
time: 97ms
memory: 51808kb

input:

8 884152939068009488

output:

32 87

result:

ok single line: '32 87'

Test #14:

score: 0
Accepted
time: 52ms
memory: 39404kb

input:

10 334992255296783634

output:

1 2

result:

ok single line: '1 2'

Test #15:

score: 0
Accepted
time: 66ms
memory: 42316kb

input:

9 387165762000719100

output:

9 26

result:

ok single line: '9 26'

Test #16:

score: 0
Accepted
time: 61ms
memory: 40640kb

input:

13 966426794141592430

output:

5 23

result:

ok single line: '5 23'

Test #17:

score: 0
Accepted
time: 66ms
memory: 38820kb

input:

30 3882204456

output:

impossible

result:

ok single line: 'impossible'

Test #18:

score: 0
Accepted
time: 60ms
memory: 38676kb

input:

17 388292937745500

output:

impossible

result:

ok single line: 'impossible'

Test #19:

score: -100
Time Limit Exceeded

input:

7 77777777777777777

output:


result: