※ 引述《smartboy (小光光)》之銘言：
: H 線性代數問題, 解法可能跟同餘系 matrix/inverse/determine 有關
: 題目有怪條件: sly number in set {0,1,2} 不知道怎麼用
提供一個想法, 不確定這個方向夠不夠好
N=5 for example:
C[0] = A[0]B[0] + A[1]B[4] + A[2]B[3] + A[3]B[2] + A[4]B[1]
C[1] = A[0]B[1] + A[1]B[0] + A[2]B[4] + A[3]B[3] + A[4]B[2]
C[2] = A[0]B[2] + A[1]B[1] + A[2]B[0] + A[3]B[4] + A[4]B[3]
C[3] = A[0]B[3] + A[1]B[2] + A[2]B[1] + A[3]B[0] + A[4]B[4]
C[4] = A[0]B[4] + A[1]B[3] + A[2]B[2] + A[3]B[1] + A[4]B[0]
C[0] A[1] A[2] A[3] A[4] A[0] | B[4]
C[1] A[2] A[3] A[4] A[0] A[1] | B[3]
C[2] = A[3] A[4] A[0] A[1] A[2] | B[2] ( matrix representation )
C[3] A[4] A[0] A[1] A[2] A[3] | B[1]
C[4] A[0] A[1] A[2] A[3] A[4] | B[0]
其中 A 已知, C[0] = 1 (mod Q), C[i] = 0 (mod Q) for 0<i<N
考慮把四個式子加在一起會得到
4 4 4
sigma C[i] = ( sigma A[i] ) * ( sigma B[i] ) (mod Q)
i=0 i=0 i=0
4
但是 sigma C[i] = 1 (mod Q), 所以顯然
i=0
4
gcd (sigma A[i], Q) = 1, 否則會無解! ( a simple test here )
i=0
4 4
又從上式得知, sigma A[i] 可以求 inv, 所以 sigma B[i] = A^(-1) (mod Q)
i=0 i=0
我不確定拿這一個東西回去和原本的式子線性組合會不會有什麼好性質
不過各個 digit 只能有 {0,1,2} 應該能有不錯的應用, 大家繼續想一想吧~
( 或許能把 {0,1,2} 換成 {-1,0,1} 也會有好應用? ^^" )
--
有時候，遺忘，是令人快樂的。什麼時候？當然是有人傷了你的心的時候。
存心傷你的那個人，固然是故意和你過不去，但是被傷了心而耿耿於懷的你
，卻是和自己過不去了。所以，記性不好的人，通常會是比較快樂的人，也
是比較不容易被擊倒的人。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.37
※ 編輯: ledia 來自: 140.112.30.37 (10/19 15:10)
※ 編輯: ledia 來自: 140.112.30.37 (10/19 15:10)
※ 編輯: ledia 來自: 140.112.30.37 (10/19 15:15)
※ 編輯: ledia 來自: 140.112.30.37 (10/19 15:52)
※ 編輯: ledia 來自: 140.112.30.37 (10/20 09:39)