矩陣翻硬幣

本文轉(zhuǎn)自?https://blog.csdn.net/xiaofengcanyuelong/article/details/79255105
小明先把硬幣擺成了一個 n 行 m 列的矩陣。

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

對第x行第y列的硬幣進(jìn)行 Q 操作的定義：將所有第 i*x 行，第 j*y 列的硬幣進(jìn)行翻轉(zhuǎn)。

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

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

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

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

【數(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；
對于10%的數(shù)據(jù)，n、m <= 10^1000（10的1000次方）。

資源約定：
峰值內(nèi)存消耗（含虛擬機(jī)） < 256M
CPU消耗 < 2000ms

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

題解：

　　

Q 操作的定義：將所有第 i*x 行，第 j*y 列的硬幣進(jìn)行翻轉(zhuǎn)。
(一)、找規(guī)律。
1、先看1行m列的矩陣,因?yàn)橹挥?行,當(dāng)對其進(jìn)行Q操作的時候,i和x都只能為1,
假設(shè)m為5,在對1行5列的矩陣的每個元素進(jìn)行了Q操作后,推導(dǎo)過程如下:
初始狀態(tài):1 1 1 1 1
對(1,1)元素進(jìn)行Q操作,此時變成0 0 0 0 0
對(1,2)元素進(jìn)行Q操作,此時變成0 1 0 1 0
對(1,3)元素進(jìn)行Q操作,此時變成0 1 1 1 0
對(1,4)元素進(jìn)行Q操作,此時變成0 1 1 0 0
對(1,5)元素進(jìn)行Q操作,此時變成0 1 1 0 1
綜上,可以看出,這五個元素分別翻轉(zhuǎn)了1,2,2,3,2次,很明顯,當(dāng)進(jìn)行奇數(shù)次翻轉(zhuǎn)后為0,當(dāng)進(jìn)行偶數(shù)次翻轉(zhuǎn)后變?yōu)?。那么,我們?nèi)绻笞罱K有幾個0,便是求有幾個位置可以進(jìn)行奇數(shù)次翻轉(zhuǎn)。
首先,設(shè)1<=x<=m,對于(1,m)矩陣中的(1,x)硬幣,它翻轉(zhuǎn)了奇數(shù)次呢?還是偶數(shù)次呢?這時回看到Q操作的定義,會發(fā)現(xiàn)這樣一個規(guī)律:(1,x)位置翻轉(zhuǎn)的次數(shù)等于x的約數(shù)個數(shù),且當(dāng)x=k^2(k=1,2,3,4,5,6)時,翻轉(zhuǎn)次數(shù)為奇數(shù)次,否則為偶數(shù)次。
如1行5列矩陣中:
1的約數(shù)只有1個,因此(1,1)翻轉(zhuǎn)了1次,
2的約數(shù)有2個,因此(1,2)翻轉(zhuǎn)了2次,
3的約數(shù)有2個,因此(1,3)翻轉(zhuǎn)了2次,
4的約數(shù)有3個,因此(1,4)翻轉(zhuǎn)了3次,
5的約數(shù)有2個,因此(1,5)翻轉(zhuǎn)了2次。
當(dāng)k=1,2時,即x=1,4時翻轉(zhuǎn)奇數(shù)次,其他為偶數(shù)次。

綜上,一個(1,m)矩陣在對每一個元素都進(jìn)行Q操作后,0的個數(shù)為根號下m。

2、那么(n,m)矩陣呢?這里不再贅述,找個簡單的矩陣再走一遍流程就會得到下面的結(jié)論。
一個(n,m)矩陣在對每一個元素都進(jìn)行Q操作后,0的個為根號下n乘以根號下m
參考:http://blog.csdn.net/snailset/article/details/26752435

(二)、處理大數(shù)開根。
對于100%的數(shù)據(jù)，n、m <= 10^1000(10的1000次方)。
n,m的最大值是10^1000次方,那么普通的開根已經(jīng)不適用于這種情況了,在Java中有BigInteger和BigDecimal可以滿足這樣大數(shù)開根的需求。
參考:https://www.cnblogs.com/Annetree/p/6664383.html
最后得出以下代碼:

1 public class Demo { 2 3 public static void main(String[] args) { 4 5 Scanner scanner = new Scanner(System.in); 6 BigInteger n = scanner.nextBigInteger(); 7 BigInteger m = scanner.nextBigInteger(); 8 BigInteger tem = sqrt(n).multiply(sqrt(m)); 9 System.out.println(tem); 10 11 } 12 //大數(shù)開根--->折半查找法 13 static BigInteger sqrt(BigInteger x) { 14 BigInteger l = BigInteger.ONE; 15 BigInteger r = x; 16 BigInteger temp = BigInteger.ZERO;// 0 17 while (!l.equals(r)) { 18 BigInteger mid = (l.add(r)).divide(BigInteger.valueOf(2));// (l+r)/2 19 // temp!=0&&temp==mid---->mid!=0 20 if (temp.compareTo(BigInteger.ZERO) != 0 && temp.compareTo(mid) == 0) { 21 break; 22 } else { 23 temp = mid; 24 } 25 if (temp.compareTo(BigInteger.ZERO) == 0) { 26 temp = mid; 27 } 28 // mid*mid>x 29 if (mid.multiply(mid).compareTo(x) == 1) { 30 r = mid; 31 } else { 32 l = mid; 33 } 34 } 35 if (l.multiply(l).compareTo(x) == 1) { 36 l = l.subtract(BigInteger.ONE); 37 } 38 return l; 39 40 } 41 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/1013star/p/10332115.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯 矩阵翻硬币的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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