題目要求

P2651題目鏈接

分析

一道數(shù)論題呢……

a₁/a₂/a₃/…/a_n這個(gè)數(shù)吧，可以變變形：
因?yàn)榭筛淖冇?jì)算順序，表達(dá)式的值一定可以寫成一些a_i的乘積除以剩下數(shù)的乘積。
顯然，(a₁/a₂)是一個(gè)整體，a₂必須放在最后的分母上，表達(dá)式寫成a₁/(a₂/a₃…/a_i)=a₁a₃…a_i/a₂。

這個(gè)表達(dá)式求值最終就是最大值，要想得到最大整數(shù)就判斷a₁a₃…a_i這個(gè)整數(shù)能不能整除a₂。

判斷整除不可以算a₁a₃…a_i，因?yàn)榭隙ǔ秶?#xff0c;long不夠是肯定的，BigInteger沒(méi)必要，就需要我們換思路。

思路就是分別用計(jì)算a₁a₃…a_i中每個(gè)因子與a₂的最大公約數(shù)，此時(shí)用輾轉(zhuǎn)相除法，寫一下gcd()算法就行了。

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

最終看看能不能將a₂約成1，就可以進(jìn)行判斷Yes or No了呢。

并不需要求值，所以就按照這么個(gè)思路走吧。

需要注意的是，當(dāng)a_i與a₂的最大公約數(shù)是1的時(shí)候，不能約分，不要強(qiáng)除a_i/a₂，否則得到小數(shù)就涼了……
我們可以逐步用自除即/=的方式逐步消掉a₂，每次除gcd，不要直接與a_i基礎(chǔ)，這樣可以防止出現(xiàn)小數(shù)。
（我下面的代碼有一處寫的判a₂/gcd能不能整除，其實(shí)回頭看，沒(méi)必要，因?yàn)榭隙苷穆?#xff09;
還需要注意，在a₂得到1以后就停下流程，不要繼續(xù)除下去，否則會(huì)崩盤的。

AC代碼（Java語(yǔ)言描述）

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

總結(jié)

以上是生活随笔為你收集整理的加括号改变连除式结果（洛谷P2651题题解，Java语言描述）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。