题目要求

P2651题目链接

分析

一道数论题呢……

a₁/a₂/a₃/…/a_n这个数吧，可以变变形：
因为可改变计算顺序，表达式的值一定可以写成一些a_i的乘积除以剩下数的乘积。
显然，(a₁/a₂)是一个整体，a₂必须放在最后的分母上，表达式写成a₁/(a₂/a₃…/a_i)=a₁a₃…a_i/a₂。

这个表达式求值最终就是最大值，要想得到最大整数就判断a₁a₃…a_i这个整数能不能整除a₂。

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

思路就是分别用计算a₁a₃…a_i中每个因子与a₂的最大公约数，此时用辗转相除法，写一下gcd()算法就行了。

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

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

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

需要注意的是，当a_i与a₂的最大公约数是1的时候，不能约分，不要强除a_i/a₂，否则得到小数就凉了……
我们可以逐步用自除即/=的方式逐步消掉a₂，每次除gcd，不要直接与a_i基础，这样可以防止出现小数。
（我下面的代码有一处写的判a₂/gcd能不能整除，其实回头看，没必要，因为肯定能整除的嘛）
还需要注意，在a₂得到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);}} }

总结

以上是生活随笔为你收集整理的加括号改变连除式结果（洛谷P2651题题解，Java语言描述）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。