Давхар утга (Open Cup Mongolia)

Юуны өмнө сонирхолтой бодлогууд бэлдэж оруулсан найздаа баярлалаа.

Миний хувьд хамгийн таалагдсан бодлого нь давхар утга байсан. Ерөнхийдөө 2 талаасаа зааглагдсан бодлогыг 1 талаасаа зааглагдсан 2 ширхэг бодлого руу шилжүүлэх нь ашигтай байдаг. Count(A..B) = Count(1..B) - Count(1..A-1). Тэгэхээр шинэ бодлого маань давхар утга нь 1..N хооронд байдаг тоонуудыг тоолох бодлоготой тэнцүү.

• Ямар ч тооны давхар утга нь өөрөөс нь багагүй байх учир бидний хайж байгаа тоо 1..N хооронд байна
• Бодлогын нөхцлийг хангах тоо 0 цифр агуулахгүй
• Бодлогын нөхцлийг хангах тоонуудын цифрүүдийн үржвэрийн олонлог нь хамгийн ихдээ 36100 элемэнттэй байна

Эхний 2 нөхцөл илэрхий, гэхдээ 3 дахь нөхцөл бага зэргийн таамаглал + brute force шаардана.
Цифрүүдийн үржвэрүүд хамгийн ихдээ 36100 янз байж болох учраас бид аль нэг үржвэрийг бэхлэж аваад (P гэе) цифрүүдийн үржвэр нь P тэй тэнцүү байдаг floor(N/P) -с хэтэрдэггүй тоонуудыг тоолоход хангалттай.

Бидний дараагийн бодолтонд хэрэг болох *шидэт* функц зохиоё.
f(n,p) = n оронтой цифрүүдийн үржвэр нь p байдаг тоонуудын тоо.

Бид X тооноос хэтэрдэггүй цифрүүдийн үржвэр нь P байдаг тоонуудын тоог олох гэж байна. X тоог D1D2D3...DK гэсэн K оронтой тоо гэж үзье. Тэгвэл K-аас цөөн оронтой бүх тоо манай нөхцлийг хангана. Энэ тохиолдолд бид f(1,P)+f(2,P)+...+f(K-1,P) гэсэн нийлбэрээр тоолно. Одоо бид яг K оронтой бөгөөд D1D2D3...DK тооноос хэтрэхгүй тоонуудыг тоолох үлдэж байна
Хэрвээ бид K оронтой тооны эхний оронгоор D1-с бага цифр сонговол үлдсэн K-1 цифрээс үл хамааран уг тоо D1D2D3...DK тооноос хэтрэхгүй. Эхний оронд D<D1 байх D цифр сонгосон гэж үзвэл P үржвэр маань P/D болоод дэд бодлого нь f(k-1,P/D) болж шийдэгдэнэ. Одоо тэгвэл эхний цифр D1 байна гэж үзээд дараагийн оронд D<D2 байх D цифр сонговол үлдсэн K-2 цифрээс үл хамааран уг тоо хэтрэхгүй ба энэ үед f(k-2,P/D1/D) болох юм. Энэ санаагаар бид дээд хязгаарын асуудлыг шийдэж байгаа юм.

Шидэт функц
f(n,p) = Sum(f(n-1,p/x)) { x=1..9 && p % x == 0 }