加括号改变连除式结果(洛谷P2651题题解,Java语言描述)

题目要求

P2651题目链接
加括号改变连除式结果(洛谷P2651题题解,Java语言描述)

分析

一道数论题呢……

a1/a2/a3/…/an这个数吧,可以变变形:
因为可改变计算顺序,表达式的值一定可以写成一些ai的乘积除以剩下数的乘积。
显然,(a1/a2)是一个整体,a2必须放在最后的分母上,表达式写成a1/(a2/a3…/ai)=a1a3…ai/a2

这个表达式求值最终就是最大值,要想得到最大整数就判断a1a3…ai这个整数能不能整除a2

判断整除不可以算a1a3…ai,因为肯定超范围,long不够是肯定的,BigInteger没必要,就需要我们换思路。

思路就是分别用计算a1a3…ai中每个因子与a2的最大公约数,此时用辗转相除法,写一下gcd()算法就行了。

private static long gcd(long a,long b) {
    return b == 0 ? a : gcd(b, a % b);
}

最终看看能不能将a2约成1,就可以进行判断Yes or No了呢。

并不需要求值,所以就按照这么个思路走吧。

需要注意的是,当ai与a2的最大公约数是1的时候,不能约分,不要强除ai/a2,否则得到小数就凉了……
我们可以逐步用自除即/=的方式逐步消掉a2,每次除gcd,不要直接与ai基础,这样可以防止出现小数。
(我下面的代码有一处写的判a2/gcd能不能整除,其实回头看,没必要,因为肯定能整除的嘛)
还需要注意,在a2得到1以后就停下流程,不要继续除下去,否则会崩盘的。

AC代码(Java语言描述)

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static long gcd(long a,long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int times = scanner.nextInt();
        List<String> list = new ArrayList<>();
        for (int i = 0; i < times; i++) {
            int num = scanner.nextInt();
            long a1 = scanner.nextLong();
            long a2 = scanner.nextLong();
            long gcd = gcd(a1, a2);
            if (a2 % gcd == 0) {
                a2  /= gcd(a1, a2);
            }
            int j;
            for (j = 2; j < num && a2 > 1; j++) {
                long aj = scanner.nextLong();
                gcd = gcd(aj, a2);
                if (a2 % gcd == 0) {
                    a2 /= gcd;
                }
            }
            for (; j < num; j++) {
                scanner.nextInt();
            }
            if (a2 == 1) {
                list.add("Yes");
            } else {
                list.add("No");
            }
        }
        scanner.close();
        for (String s : list) {
            System.out.println(s);
        }
    }
}

猜你喜欢