QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#267188#5103. Fair DivisionjuampiWA 67ms39524kbJava82.6kb2023-11-27 01:07:152023-11-27 01:07:15

Judging History

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

  • [2023-11-27 01:07:15]
  • 评测
  • 测评结果:WA
  • 用时:67ms
  • 内存:39524kb
  • [2023-11-27 01:07:15]
  • 提交

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};
    }
}

详细

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'