Skip to content

Instantly share code, notes, and snippets.

@SansWord
Created June 14, 2016 10:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save SansWord/6579a81c7b58ac09eaa0d9a272d6e11e to your computer and use it in GitHub Desktop.
Save SansWord/6579a81c7b58ac09eaa0d9a272d6e11e to your computer and use it in GitHub Desktop.
根據題目分析,先按照餘數分類:
假設答案為 N
mod 1,3,7,9 餘 0 ........ (1)
mod 2,4,5,8 餘 1 ........ (2)
mod 6 餘 3 .............. (3)
lcm(3,7,9) = 63 ......... (4), by (1)
lcm(2,4,5,8) = 40 ....... (5), by (2)
N ≡ 0 mod 63 ..... (6), by (4)
N ≡ 1 mod 40 ..... (7), by (5)
N ≡ 3 mod 6 ....... (8), by (3)
Solve integer m,n,l
N = 63m ........... (9), by (6)
= 40n + 1 ....... (10), by (7)
= 6l + 3 ........ (11), by (8)
63m = 60m + 3m = 6l + 3 ....... by (6),(8)
3m ≡ 3 mod 6
3m = 3(2s+1) = 6s + 3 ≡ 3 mod 6
m = 2s + 1 ........ (12)
63m = 63(2s+1)
= 126s + 63
= 40(3s+1) + 6s + 23 ≡ 1 mod 40
6s + 23 ≡ 1 mod 40
6s + 23 = 40p + 1 ....... (13)
By brute force:
Given p = 1:
s = 3 ....... by (13)
m = 7 ....... by (12)
N = 63 * 7... by (6)
= 441
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment