如果某個數的平方的末尾極為數等於這個數,那麽就稱這個數為自守數。
性質壹:
n位的自守數,從首位開始去除任意位,得到的仍是自守數。
性質二:
N位的自首數只有兩個,壹個是5的M(M=2N?)次方的末N位,即5^m mod 10^N
另壹個是10^N+1減去剛才那個數,即-5^m+1 mod 10^N
在下面介紹的來自百度用戶l4m2space的方法中,羅列出了500位的尾數為5的自守數。
最完美的方法之壹:(來自百度用戶l4m2space)
Const Dig = 1000
Function ChengFa(ByVal M As String, ByVal N As String) As String
'用於大數相乘
Dim A&(), B&(), S&()
ReDim A(Len(M)), B(Len(N)), S(Len(M) + Len(N) + 1)
M = StrReverse(M)
For I = 1 To Len(M)
A(I) = Val(Mid(M, I, 1))
Next
N = StrReverse(N)
For I = 1 To Len(N)
B(I) = Val(Mid(N, I, 1))
Next
For I = 1 To Len(M)
For J = 1 To Len(N)
S(I + J) = S(I + J) + A(I) * B(J)
Next
Next
For I = 2 To Len(M) + Len(N) + 1
If S(I) > 9 Then
S(I + 1) = S(I + 1) + S(I) \ 10
S(I) = S(I) Mod 10
End If
Next
Do Until I <= 2
I = I - 1
ChengFa = ChengFa & S(I)
Loop
End Function
Private Sub Form_Load()
Dim A$, I&, T#
T = Timer
A = 5
For I = 1 To Dig
A = Right(ChengFa(A, A), Dig)
Debug.Print I
DoEvents
Next
Debug.Print A
Debug.Print Timer - T
End
End Sub
程序運行結果:66323172405515756102352543994999345608083801190741530060056055744818709692785099775918050075416428527708162011350246806058163276171676765260937528056844214486193960499834472806721906670417240094234466197812426690787535944616698508064636137166384049029219341881909581659524477861846140912878298438431703248173428886572737663146519104988029447960814673760503957196893714671801375619055462996814764263903953007319108169802938509890062166509580863811000557423423230896109004106619977392256259918212890625
程序運行參考時間:61.186593749997 s
另摘錄幾個網上的答案,供參考。
方法壹:
Private Sub Form_click()
For k = 0 To 2000
If k = CInt(Right(CStr(k ^ 2), Len(CStr(k)))) Then Print k
Next k
End Sub
方法二:
Private Sub Command1_Click()
For i = 0 To 2000
j = i * i
k = i
Do While k > 0 And k Mod 10 = j Mod 10
k = k \ 10
j = j \ 10
Loop
If k = 0 Then Print i
Next i
End Sub
方法三:來自百度用戶bz3zwy
註:也就是已知n為自守數,只要確定其前面再加的壹個數字即可。於是可得如下算法:
Option Explicit
Const Max& = 8
Dim a#(Max), c#(Max)
Dim i&, total&, S#
Private Sub Command1_Click()
a(0) = 1
For i = 1 To Max
a(i) = a(i - 1) * 10
Next
c(0) = 0
total = 0
work (1)
End Sub
Sub work(i&)
Dim j&
If i = Max Then Exit Sub
For j = 0 To 9
c(i) = a(i - 1) * j + c(i - 1)
S = c(i) * c(i)
If S - Int(S / a(i)) * a(i) = c(i) Then
If j > 0 Then
total = total + 1
Print total; c(i); S
End If
work (i + 1)
End If
Next
End Sub
方法四:來自百度用戶bz3zwy,博主稱,由 仙劍魔 (福爾魔劍(HolMoJan)) 提供
[原理分析]:
假設a為n位十進制數
若a為自守數,則a*a mod 10^n=a
令p=10^n,k=a*a\p
則a*a=k*p+a
即a*(a-1)=k*p=k*10^n
於是得出判定依據
如果a*(a-1)內2,5的因子數均>=n,則a為自守數
a和a-1,壹個奇數壹個偶數
所以2是完全由偶數提供的
即偶數必定是2^n*t的形式
剛才說了a和a-1是壹奇數壹偶數
2的因子全在偶數裏
那麽若偶數裏同時有5的因子,可能嗎?
假設壹個數字(0除外)末尾有m個0,那麽他平方後末尾就會有2m個0
所以可以得出結論:偶數裏沒有因子5
即因子5全部在奇數裏
則奇數必定是5^n*r的形式
[編程者感言]
其實數學相關的題目
如果能推導出有用的信息以及結論
就能得到壹些簡單快速的算法
壹開始只是試著算下的
直到推出這個a*(a-1)=k*p=k*10^n式子的時候我覺得可能會有用
後來討論出了2,5因子的情況,算法就基本成型了
其實這裏用基2也能算,只要交換下i,j的累乘值
但是可以發現基5的速度快得多,省去了不少計算
[基5的測試代碼]
Dim n As Long, t As Long, i As Long, j As Long, a As Long
i = 1
j = 1
Print 0
For n = 1 To 7
i = i * 5
j = j * 2
For t = (10 ^ (n - 1) - 1) \ i + 1 To (10 ^ n - 1) \ i
a = i * t
If (a + 1) Mod j = 0 Then
Print a + 1
End If
If (a - 1) Mod j = 0 Then
Print a
End If
NextNext