標題：矩陣翻硬幣

小明先把硬幣擺成了一個 n 行 m 列的矩陣。

隨后，小明對每一個硬幣分別進行一次 Q 操作。

對第x行第y列的硬幣進行 Q 操作的定義：將所有第 ix 行，第 jy 列的硬幣進行翻轉。

其中i和j為任意使操作可行的正整數(shù)，行號和列號都是從1開始。

當小明對所有硬幣都進行了一次 Q 操作后，他發(fā)現(xiàn)了一個奇跡——所有硬幣均為正面朝上。

小明想知道最開始有多少枚硬幣是反面朝上的。于是，他向他的好朋友小M尋求幫助。

聰明的小M告訴小明，只需要對所有硬幣再進行一次Q操作，即可恢復到最開始的狀態(tài)。然而小明很懶，不愿意照做。于是小明希望你給出他更好的方法。幫他計算出答案。

【數(shù)據(jù)格式】

輸入數(shù)據(jù)包含一行，兩個正整數(shù) n m，含義見題目描述。

輸出一個正整數(shù)，表示最開始有多少枚硬幣是反面朝上的。

【樣例輸入】

2 3

【樣例輸出】

1

【數(shù)據(jù)規(guī)模】

對于10%的數(shù)據(jù)，n、m <= 10^3；

對于20%的數(shù)據(jù)，n、m <= 10^7；

對于40%的數(shù)據(jù)，n、m <= 10^15；

對于100%的數(shù)據(jù)，n、m <= 10^1000(10的1000次方)。

資源約定：

峰值內存消耗(含虛擬機) < 256M

CPU消耗 < 2000ms

請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入...” 的多余內容。

所有代碼放在同一個源文件中，調試通過后，拷貝提交該源碼。

注意：不要使用package語句。不要使用jdk1.7及以上版本的特性。

注意：主類的名字必須是：Main，否則按無效代碼處理。

解析：

方案一：

題目中提示：“聰明的小M告訴小明，只需要對所有硬幣再進行一次Q操作，即可恢復到最開始的狀態(tài)。”

即假設所有格子硬幣都是正面的，反向進行上述分析的模擬。

Scanner input = new Scanner(System.in);

int n = input.nextInt(); //硬幣矩陣n行

int m = input.nextInt(); //硬幣矩陣m列

int[][] arr = new int[n+1][m+1]; //定義硬幣(數(shù)組大小+1的原因和題意相符，下標從1開始)

//將所有硬幣變成正面(1：正面；0：反面)

for (int x = 1; x <= n; x++) {

for (int y = 1; y <= m; y++) {

arr[x][y] = 1;

}

}

//模擬Q操作

for (int x = 1; x <= n; x++) {

for (int y = 1; y <= m; y++) {

//循環(huán)行號和列好的倍數(shù)

for (int i = 1; i*x <= n; i++) {

for (int j = 1; j*y<=m; j++) {

int temp = arr[i*x][j*y];

arr[i*x][j*y] = temp==1?0:1;

}

}

}

}

int count = 0; //假設反面的數(shù)量為0

for (int x = 1; x <= n; x++) {

for (int y = 1; y <= m; y++) {

if(arr[x][y] == 0)

count++;

}

}

System.out.println(count);

由于題目有專門的描述如下：

【數(shù)據(jù)規(guī)模】

對于10%的數(shù)據(jù)，n、m <= 10^3；

對于20%的數(shù)據(jù)，n、m <= 10^7；

對于40%的數(shù)據(jù)，n、m <= 10^15；

對于100%的數(shù)據(jù)，n、m <= 10^1000(10的1000次方)。

資源約定：

峰值內存消耗(含虛擬機) < 256M

CPU消耗 < 2000ms

則表示此題對執(zhí)行效率有一定的要求，而進行方案一進行模擬的形式，如果數(shù)據(jù)量大的情況下，效率低，不能完全滿足題目的要求。

方案二：

假設硬幣舉證如下，模擬所有硬幣Q操作翻轉過程如下：

1 2 3

4 5 6

7 8 9

對第一個硬幣Q操作，需要翻轉硬幣：1，2，3，4，5，6，7，8，9(即全部)

對第二個硬幣Q操作，需要翻轉硬幣：2，5，8

對第三個硬幣Q操作，需要翻轉硬幣：3，6，9

對第四個硬幣Q操作，需要翻轉硬幣：4，5，6

對第五個硬幣Q操作，需要翻轉硬幣：5

對第六個硬幣Q操作，需要翻轉硬幣：6

對第七個硬幣Q操作，需要翻轉硬幣：7，8，9

對第八個硬幣Q操作，需要翻轉硬幣：8

對第九個硬幣Q操作，需要翻轉硬幣：9

思路：

(1)每個硬幣，如果知道被翻轉了幾次，則可以求出該硬幣初始狀態(tài)是正面還是反面，翻轉了奇數(shù)次硬幣初始為反面，翻轉了偶數(shù)次硬幣為正面。

(2)通過上述數(shù)據(jù)得出規(guī)律，翻轉次數(shù)=行號的約數(shù)個數(shù)*列號的約數(shù)個數(shù)，即：

第一個硬幣，行號為1(約數(shù)1，只有1個)，列號為1(約數(shù)1，只有1個)，翻轉數(shù)量=1*1=1

第二個硬幣，行號為1(約數(shù)1，只有1個)，列號為2(約數(shù)1，2，有2個)，翻轉數(shù)量=1*2=2

第三個硬幣，行號為1(約數(shù)1，只有1個)，列號為3(約數(shù)1，3，有2個)，翻轉數(shù)量=1*2=2

第四個硬幣，行號為2(約數(shù)1，2，有2個)，列號為1(約數(shù)1，有1個)，翻轉數(shù)量=2*1=2

第五個硬幣，行號為2(約數(shù)1，2，有2個)，列號為2(約數(shù)1，2，有2個)，翻轉數(shù)量=2*2=4

第六個硬幣，行號為2(約數(shù)1，2，有2個)，列號為3(約數(shù)1，3，有2個)，翻轉數(shù)量=2*2=4

第七個硬幣，行號為3(約數(shù)1，3，有2個)，列號為1(約數(shù)1，有1個)，翻轉數(shù)量=2*1=2

第八個硬幣，行號為3(約數(shù)1，3，有2個)，列號為2(約數(shù)1，2，有2個)，翻轉數(shù)量=2*2=4

第九個硬幣，行號為3(約數(shù)1，3，有2個)，列號為3(約數(shù)1，3，有2個)，翻轉數(shù)量=2*2=4

(3)實際上不需要求行號和列號的約數(shù)個數(shù)，只需要確定約數(shù)個數(shù)是奇數(shù)還是偶數(shù)即可，如何確定某個數(shù)字的約數(shù)個數(shù)是奇數(shù)還是偶數(shù)，有規(guī)律：平方數(shù)的約數(shù)個數(shù)是奇數(shù)，其它數(shù)字的約數(shù)個數(shù)為偶數(shù)，例如：

4約數(shù)(1，2，4)有三個為奇數(shù)；9的約數(shù)(1，3，9)有三個為奇數(shù)；16約數(shù)(1，2，4，8，16)有5個為奇數(shù)

5約束(1，5)有兩個為偶數(shù)；10約束(1，2，5，10)有四個為偶數(shù)；15約數(shù)(1，3，5，15)有四個為偶數(shù)

(4)翻轉次數(shù)=行號的約數(shù)個數(shù)*列號的約數(shù)個數(shù)；并且(奇乘奇=奇，奇乘偶=偶，偶乘偶=偶)，當結果為奇數(shù)時，初始狀態(tài)才是反面，則要求行號約數(shù)個數(shù)和列號的約數(shù)個數(shù)都為奇數(shù)，則要求行號和列號都為平方數(shù)。

(5)即題目含義變成了求行號范圍內有幾個平方數(shù)，列號范圍內有幾個平方數(shù)，結果為兩個數(shù)字的乘積。

(6)如果循環(huán)遍歷行號和列號求含有平方數(shù)的個數(shù)，效率仍然很低下，有規(guī)律：某個數(shù)字內平方數(shù)的個數(shù)等于該數(shù)字的開方取整，例如：

9里面(1，4，9)三個平方數(shù)，9的開方也等于三；

20里面(1，4，9，16)四個平方數(shù)，20的開方然后取整等于四。

(7)我們得到結論：初始為反面的個數(shù)=行號的開方+列號的開方。

(8)由于行號和列號范圍可以為(10的1000次方)，直接用數(shù)字類型無法表示，無法使用Math.sqrt進行開方，只能將數(shù)字做為字符串進行處理。

(9)當數(shù)字字符串的長度為偶數(shù)，則開方結果的長度為(本身長度/2)；當數(shù)字字符串的長度為奇數(shù)，則開方結果的長度為(本身長度/2+1),例如：

99長度為2，開方取整為9，長度為1；100長度為3，開方結果為10，長度為2；

(10)確定了開方長度之后，利用BigInteger和char[]數(shù)組，確定數(shù)組每一位數(shù)字求出開方結果。

public static void main(String[] args) {

Scanner input = new Scanner(System.in);

String n = input.next(); //硬幣矩陣n行

String m = input.next(); //硬幣矩陣m列

BigInteger rowSqrt = sqrt(n);

BigInteger colSqrt = sqrt(m);

System.out.println(rowSqrt.multiply(colSqrt));

}

public static BigInteger sqrt(String s)

{

//數(shù)字字符串的長度為偶數(shù)，則開方結果的長度為(本身長度/2)；

//當數(shù)字字符串的長度為奇數(shù)，則開方結果的長度為(本身長度/2+1)

int len = s.length() % 2 == 0 ? s.length()/2 : s.length()/2+1; //求開方之后的字符串長度

char[] arr = new char[len]; //定義字符數(shù)組用于存放開方后的字符串

Arrays.fill(arr,'0'); //將字符數(shù)組所有元素設置為'0'

BigInteger num = new BigInteger(s); //將字符串轉成BigInteger類型

for (int i = 0; i < arr.length; i++)

{

//循環(huán)確定字符數(shù)組每一位的數(shù)字

for (char c = '0'; c <= '9'; c++)

{

arr[i] = c;

BigInteger sqrtNum = new BigInteger(String.valueOf(arr));

if(sqrtNum.pow(2).compareTo(num) == 1) //當前假設數(shù)字的平方超過了數(shù)字本身，則減1操作

{

arr[i] -= 1;

break;

}

}

}

return new BigInteger(String.valueOf(arr));

}

總結

以上是生活随笔為你收集整理的Java输出小明算对多少题目_2014年Java方向C组第十题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。