同余在NOIP中壹般怎麽考?
lz妳好。
首先說壹下基本的運算性質吧,主要就是模加法、減法、乘法和乘法逆元(也可以理解成除法),相信這些問題lz應該都有了解,如果覺得有問題可以參考Matrix67神犇的博文《同余運算及其基本性質》(在百度按關鍵詞搜索即可,抱歉沒法發鏈接。)
然後是壹些基本的定理:最基本的比如擴展歐幾裏得定理(參見noip2012 Day2T1,不過考得非常簡單,建議還是把擴展歐幾裏德完整的弄明白)、求乘法逆元、快速冪(參見noip2013 Day1T1)、費馬小定理、歐拉定理、中國剩余定理,等等。
如果lz是在競賽強省,最好掌握壹些略微復雜壹點的定理/算法,雖然noip不會用到,但多了解壹些總是好的,而且如果lz要參加省選可以省很多麻煩。如:離散對數求法(Shank大步小步攻擊算法)、原根相關問題,等等。可以參考劉汝佳的《入門經典訓練指南》第二章。
noip涉及到的數論知識還是非常少的,壹般只要知道相關定理/算法就能把題目解決,很少有隱藏得比較深的模型,如果出題也就是考比較模板的內容。
蒟蒻我是noip2012/noip2013/NOI2014選手,最後noi銅滾粗了……祝lz好運,取得滿意的成績!