Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:相当简单的 O(1) 算法！

Posted by Xz20011115 at 2019-05-15 14:23:23 on Problem 1019
In Reply To:相当简单的 O(1) 算法！ Posted by:Xz20011115 at 2019-05-15 13:25:47
```我的算法其实主要是利用一些数学知识。

A:  1 <= n < 10
la(n) = 1
lb(n) = Σ(la(k)) (k=1...n)
= Σ(1) (k=1...n)
= n
lc(n) = Σ(lb(k)) (k=1...n)
= Σ(k) (k=1...n)
= (n+1)*n/2
lb(9) = 9
lc(9) = 45
解方程 lc(x) = i-1 得
x = sqrtl(i*2-1.75)-.5
解方程 lb(x) = i-1 得
x = i

B: 10 <= n < 100
la(n) = 2
lb(n) = Σ(la(k)) (k=1...n)
= lb(9) + Σ(la(k)) (k=10...n)
= 9 + Σ(2) (k=10...n)
= 2n-9
lc(n) = Σ(lb(k)) (k=1...n)
= lc(9) + Σ(lb(k)) (k=10...n)
= 45 + Σ(2k-9) (k=10...n)
= (n-8)*n+36
lb(99) = 189
lc(99) = 9045
解方程 lc(x) = i-1 得
x = sqrtl(i-21)+4
解方程 lb(x) = i-1 得
x = (i+10)/2

C: 100 <= n < 1000
la(n) = 3
lb(n) = Σ(la(k)) (k=1...n)
= lb(99) + Σ(la(k)) (k=100...n)
= 189 + Σ(3) (k=100...n)
= 3n-108
lc(n) = Σ(lb(k)) (k=1...n)
= lc(99) + Σ(lb(k)) (k=100...n)
= 9045 + Σ(3k-108) (k=100...n)
= (n*3-213)*n/2+4887
lb(999) = 2889
lc(999) = 1395495
解方程 lc(x) = i-1 得
x = (sqrtl(i*6-17985.75)+106.5)/3
解方程 lb(x) = i-1 得
x = (i+110)/3

D: 1000 <= n < 10000
la(n) = 4
lb(n) = Σ(la(k)) (k=1...n)
= lb(999) + Σ(la(k)) (k=1000...n)
= 2889 + Σ(4) (k=1000...n)
= 4n-1107
lc(n) = Σ(lb(k)) (k=1...n)
= lc(999) + Σ(lb(k)) (k=1000...n)
= 1395495 + Σ(4n-1107) (k=1000...n)
= (n*2-1105)*n+503388
lb(9999) = 38889
lc(9999) = 189414495
解方程 lc(x) = i-1 得
x = sqrtl(i*.5-175385.4375)+276.25
解方程 lb(x) = i-1 得
x = (i+1110)/4

E: 10000 <= n < 100000
la(n) = 5
lb(n) = Σ(la(k)) (k=1...n)
= lb(9999) + Σ(la(k)) (k=10000...n)
= 38889 + Σ(5) (k=10000...n)
= 5n-11106
lc(n) = Σ(lb(k)) (k=1...n)
= lc(9999) + Σ(lb(k)) (k=10000...n)
= 189414495 + Σ(5n-11106) (k=10000...n)
= (n*5-22207)*n/2+50488389
lb(99999) = 488889
lc(99999) = 23939649495
解方程 lc(x) = i-1 得
x = sqrtl(i*.4-15263847.51)+2220.7
解方程 lb(x) = i-1 得
x = (i+11110)/5

Followed by: