number theory

Анхны тоо Анхы тоо гэдэг нь яг 2 ширхэг ялгаатай хуваагчтай натурал тоог хэлдэг. Жишээ нь 2, 3, 5, 7 гэх мэт үргэлжлээд явна. N гэсэн тоо өгөгдөхөд тухайн тоог анхны тоо эсэхийг хэрхэн мэдэх вэ? Мэдээж бид [1, N] завсарт гүйгээд N тоог маань хэд нь хувааж байгаа вэ гэдгийг тоолоход болно. Үүнээс хурднаар шалгаж чадах уу? Анхны тоо зөвхөн 2 хуваагчтай гэхээр 1 болон өөртөө л хуваагддаг гэсэн үг ба N тоог [2, N-1] завсарт ямар ч тоо хуваадаггүй бол анхны тоо мөн....

Бодлого A тооны B зэргийг 10^9+7 гэх анхны тоонд модулдаж гарсан хариуг ол. A, B<=10^13 Бид энгийн давталт ашиглан үүнийг олж чадна. Өөрөөр хэлбэл A тоог B удаа үржүүлэх ба энэ нь бид 10^13 удаа үржүүлэх хэмжээний зүйлийг ярьж байна. Энэ нь ер нь хэр их үйлдэл вэ? Маш их ба 1 секундэнд 300сая үйлдэл хийдэг гэж төсөөлийлдөө тэгвэл 9 цаг гаруй ажиллахнээ. Бид тооны зэрэг олохын тулд 9 цаг хүлээнэ гэдэг бол тэнэг хүн тэвчээртэй гэдэг шиг л болох нь дээ...