QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#267186#5103. Fair DivisionjuampiRE 0ms0kbJava82.6kb2023-11-27 01:05:432023-11-27 01:05:44

Judging History

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

  • [2023-11-27 01:05:44]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-11-27 01:05:43]
  • 提交

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

output:


result: