2-р сарын тэмцээн Бодолт - 2

Happy Single`s Day
Уг бодлогын санаа "Авсаархан Шийдлүүд - 1" бичлэг дээр бичигдчихсэн байв :)

Болхи тоо
(1<=Ni<=10000) гэдгээс F(N) < 2^63 байх юм. (Үүнийг тооцож үзээд шалгачихаж болно) F(K) - нь болхи тоо гэдгээс F(K) * 2, F(K) * 3, F(K) * 5 нь тус тус болхи тоо гэж гарна. Энэ аргаар 2^63-аас бага бүх (~12000 ширхэг) "Болхи тоо"-г урьдчилан тооцоолж олоод эрэмбэлнэ. Ингээд эхний 10000 болхи тоо массивт хадгалаастай байх учраас бодлогын оролтонд харгалзах хариуг амархан гаргаад байж болно.

Анхны тоо шалгагч
Эх хувилбар: Spoj.pl/problems/PON
Анхны тоо шалгадаг магадлалт алгоритмууд болох "Фермагийн магадлалт шалгуур", "Миллер-Рабины магадлалт шалгуур" алинаар нь ч бодож болно. Шалгалтын үр дүнг сайжруулахыг тулд эхний цөөн хэдэн анхны тоог урьдчилан бэлтгэж тэдгээрт хуваагдаж байгаа эсэхийг шалгаж болно. (Эхний 1000 анхны тоо юм уу 10000, 100000 хүртэлх анхны тоонуудад хувааж үзэх)

Програмчлахтай холбоотой асуудал нь:
A^B mod C =-г олох явдал. (1<B, C<2^63)
Bigmod(A, B, C) = A^B mod C гэж тэмдэглэе. Дараах байдлаар програмчилж LogN хугацаанд олж болно

LONG BIGMOD(A, B, C) {  if (B mod 2 == 0) {    return SQUARE(BIGMOD(A, B/2, C)) mod C  } else {    return BIGMOD(A, B-1, C) * (A mod C) mod C  }}

Гэвч ингээд бүрэн бодогдчихгүй юм. Учир нь X*Y mod Z үйлдлийг хийх үед X*Y үйлдлийн хариу нь 2^63 зэрэгтээс халих юм. Иймээс X*Y mod Z үйлдлийг (X+...+X) mod Z (Y удаа нэмнэ) байдлаар шийдэж болно. Үүнийг мөн өмнөх зэрэг дэвшүүлэх үйлдэлтэй адилханаар LogN хугацаанд багтааж болно.

MULTIPLY_MOD(X, Y, Z) {  if (Y mod 2 == 0) {    return MULTIPLY_MOD(X, Y/2, Z) * 2 mod Z  } else {    return (MULTIPLY_MOD(X, Y-1, Z) + X) mod Z  }}

MULTIPLY_MOD(X, Y/2, Z) * 2 үйлдэл дээр бас 2^63 -ээс халих асуудал гарах боловч өгөгдлийн төрлөө "UNSIGNED LONG LONG" гэж зааж өгснөөр энэ асуудлыг тойрж болно.

Лавлагаа:
[1] Олон оронтой тооноос үлдэгдэл олох хамаагүй сонирхолтой.

2 сарын тэмцээн - бодолт 1

Хамгийн анхны тоо:

Үржвэр нь N - с хэтрэхгүй байх эхний дараалсан анхны тоонуудын үржвэр хариу болно. Төвөгтэй хэсэг нь Том тооний үйлдэл байх.

Number:

+1+2+...+N илэрхийллийг авч үзье. Ямар нэгэн +i тоог -i болговол нийт нийлбэр маань 2i -р багасах буюу тэгш байсан бол тэгш, сондгой байсан бол сондгой хэвээр үлднэ.
Иймд 1+2+...+N>=K && (1+2+...+N)%2==K%2 байх хамгийн бага N-г олоход тэр нь хариу болно.
K тоо сөрөг үед модуль аван бодоход хангалттай.

Дахиад л шадар гурван квадрат:

Тэгш өнцөгтийг N өндөртэй тэгш өнцөгт гэж үзээд доороос нь эхлэн түвшин түвшингээр дүүргэсэн гэж үзье. Тэгш өнцөгтийн эхний i-1 түвшинг бүтэн дүүргэсэн, i дэх түвшинг бүтэн эсвэл хагас дүүргэсэн боломж нь 16 хэсэгт задарна. 0000, 0001, ...., 1111.
Тэгвэл f[i][j] -р эхний i-1 түвшинг бүтэн дүүргэсэн, i дэх түвшинг j дэх дүүргэлтээр дүүргэсэн нийт боломжийг тэмдэглэе. j нь дээрх битүүдийн 10тын тооллын систем дэх дүрслэл гэж ойлго (0<=j<=15). Тэгвэл f[i][j] = f[i-1][j1] + f[i-1][j2]+... хэлбэртэй томъёо олдно. Энэ аргаар бодвол бодлогыг O(N* 16 ) хугацаанд бодож чадна. f[i] г 1*16 хэмжээс бүхий матрикс гэж үзвэл f[i] * m = f[i+1] байх m матрикс олдно. Матриксын зэргийг log-д олох аргыг хэрэглэвэл бодолт O(16*16*16*logN) болж өгөгдсөн хугацаанд хангалттай амжна.

Муруй зам:

Уг бодлогыг хүн бодоогүй учир бодолтыг бичихгүй :).