同余在NOIP中一般怎么考？RT，一般会出什么类型的
编辑： admin 2017-25-02
-
4
首先说一下基本的运算性质吧,主要就是模加法、减法、乘法和乘法逆元（也可以理解成除法）,相信这些问题lz应该都有了解,如果觉得有问题可以参考Matrix67神犇的博文《同余运算及其基本性质》（在百度按关键词搜索即可,抱歉没法发链接.）
然后是一些基本的定理：最基本的比如扩展欧几里得定理（参见noip2012 Day2T1,不过考得非常简单,建议还是把扩展欧几里德完整的弄明白）、求乘法逆元、快速幂（参见noip2013 Day1T1）、费马小定理、欧拉定理、中国剩余定理,等等.
如果lz是在竞赛强省,最好掌握一些略微复杂一点的定理/算法,虽然noip不会用到,但多了解一些总是好的,而且如果lz要参加省选可以省很多麻烦.如：离散对数求法（Shank大步小步攻击算法）、原根相关问题,等等.可以参考刘汝佳的《入门经典训练指南》第二章.
noip涉及到的数论知识还是非常少的,一般只要知道相关定理/算法就能把题目解决,很少有隐藏得比较深的模型,如果出题也就是考比较模板的内容.
蒟蒻我是noip2012/noip2013/NOI2014选手,最后noi铜滚粗了……祝lz好运,取得满意的成绩!
提示：
Noip2012同余方程
类似问题
类似问题1：考NOIP的问题我初中时自学过VB,现在比较熟练谭浩强的 和 一些 VC++现在我高一,这年的NOIP由于不知道有这回事所以错过了如果我下年去考,能考上的几率是多少?其次,我不懂那些理论性的东西.
找个教练学习吧
VC肯定不行的
要学DEV
建议用《数据结构》这本书
动归模拟图论都有
其实noip主要是看模拟和动归 这方面下功夫就好了
类似问题2：NOIP一般考哪种数学题目[数学科目]
一般会考递推、组合以及矩阵图类的数学题,递推类的可以根据平时学的数列的思路解题
类似问题3：Noip主要是考什么普及组的C++,主要考什么?
找一本红皮,一本紫皮（带光盘）,以红皮为纲要,紫皮做题.把每一个题目毕竟你初赛没进还谈什么复赛,等初赛有把握 PS：初赛有把握起码是指能考到
类似问题4：关于noip 2012 day2 同余方程的问题这道题如果求得的结果是一个负数时需要利用 同余原理 x%b+b 将x转换为正的.求这个方法是怎么推出来的.[数学科目]
a * x = 1 (mod b)等价于a * x + b * y = 1.
假设(x0, y0)是它的某一组解（可以用扩展欧几里得算法求出）,即a * x0 + b * y0 = 1,
那么有a * (x0 + k * b) + b * (y0 - k * a) = 1,其中k可以为负数、0、或正数.
所有等于x0 + k * b的数都可以是方程的解,其中最小的正整数就是(x0 % b
类似问题5：NOIP 2013提高组 同余方程若输入的是a,b那么gcd(a,b) 运算出了x,y使得ax+by=1我不明白为什么 (x mod 2b)mod b 就是题目解希望可以简单用数论证明 [数学科目]
首先求方程 ax+by=1中的x,y是扩展欧几里得算法,实际就是求的 ax mod b=1 这个问题
而这句话 (x mod d+d) mod d 与你说的 (x mod 2d) mod d 是不一样的
(x mod d+d) mod d 这样子写是主要x可能出现负数情况.运算过程先算mod,再算加法,而不是mod 2d
所以实际计算是 ((x mod d)+d) mod d
这样子负数就ok了