vJudge 273543 – 数论

  • 2018-12-01
  • 247
  • 0
  • 0

BASIC KNOWLEDGE

快速幂(mod)

乘法取模(mod)

费马小定理

假如 a 是一个整数, p 是一个质数,那么 a^{p}-ap的倍数,可以表示为

a^{p}\equiv a{\pmod {p}}

如果a不是p的倍数,这个定理也可以写成

a^{{p-1}}\equiv 1{\pmod {p}}

欧拉函数

欧拉筛法

 

 

P1  Sum

费马小定理 快速幂取模

PROBLEM

HDU – 4704

ANALYSIS

n个球放到0..n个桶的方案数(mod 1e9+7)。

\sum_{i=0}^{n-1}\binom{i}{n-1} = 2^{n-1}

费马小定理降幂。

a^n \equiv a^{n \mod {p-1}} \pmod p

证明

    \[ \left\{\begin{matrix} k = \frac{n}{p-1}\\ b = n \mod (p-1) \end{matrix}\right. \Rightarrow n = \frac{k}{p-1}\\ \]

所以

    \[ a^n \equiv a^{k * (p-1) + b} \pmod p \]

 

    \[ a^n \equiv (a^k)^{p-1}*a^b \pmod p \]

 

    \[ (a^k)^{p-1} \equiv 1 \pmod p \]

 

所以

    \[ a^n \equiv a^b \pmod p \]

 

得证

SOLUTION

 

P2 2^x mod n = 1

费马小定理 欧拉定理 素数筛 快速幂取模

PROBLEM

HDU – 1395

ANALYSIS

给出n,找出最小的x使其满足2^{x} \mod n = 1

 

假若 an互质,那么 a^{\varphi (n)}-1 可被 n n 整除。亦即

    \[a^{\varphi (n)}\equiv 1{\pmod {n}}\]

 

如果n为质数
其中 \varphi (n) 即为欧拉总计函数。如果 n为质数,那么 \varphi (n)=n-1,因此,有高斯的版本: 假若 p为质数, ap互质( a不是 p的倍数),那么 a^{p-1}\equiv 1{\pmod {p}}

这个等式在na互质的时候一定成立

在这个题目中,因为a=2

所以na不互质,除非n为偶数,当然n=1的时候需要特殊处理下,这些都是小问题,即在n为奇数(大于1)的时候一定有解。

暴力的代码太zz了。

如果当n为一个非常大的质数,那么暴力就会很慢。因为质数的欧拉函数就是质数-1。

更为高效的方法是:\varphi(n)进行质因数分解。

然后依次枚举\varphi(n)的每一个因子,同时判断这个因子x是否满足2^{x} \equiv 1 \pmod n,不断更新一个最小值,最后得到答案。

证明:

a^{x} \equiv 1 \pmod n满足这个方程的最小x称为a对模m的指数。我们记做ordm(a),如果ordm(a)==\varphi(n)则我们称a为模m的原根

有:a^{x} \equiv 1 \pmod n \Leftrightarrow ordm(a) | X

根据以上所说:a^{x} \equiv 1 \pmod n成立,那么\varphi(n) \equiv 0 \pmod {ordm(a)}也是成立的

所以ordm(a)就是\varphi(n)的一个因子

Q.E.D.

SOLUTION

 
 

P3 Dertouzos

费马小定理 素数筛

PROBLEM

HDU – 5750

ANALYSIS

x的个数,使得d< d*x< ndd*x的最大因子,设d的最小素因子为m,简单推导知x只能取[2,\min((n-1)/d, m)]中的素数,而\min((n-1)/d至多是\sqrt{n}级别,所以只需要预处理出5*10^4中所有的素数即可。

可能是我写得不好吧,最后优化了输入输出才过了的。

调了一天bug了,心态有点爆炸,打个微笑脸。

SOLUTION

 

P4 Saving Beans

费马小定理 组合数取模 卢卡斯定理 快速幂

PROBLEM

HDU – 3037

ANALYSIS

将不超过m个果子分到n个桶中的方案数(mod prime no greater than 1e5),有序,可空。

 

可用高中排列组合中隔板法解决。

另设一空桶,问题转化为将m+n+1个果子分到n+1个桶中,有序,不可空。

易得出 answer = \binom{n}{n+m}

问题转化为求 \binom{n}{n+m} \mod p

可用卢卡斯定理得出。

卢卡斯定理:

对于非负整数m和n和素数p, 同余式:

    \[ {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}, \]

成立。其中:

    \[ m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0}, \]

并且

    \[ n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0} \]

mnp进制展开。当m < n时,二项式系数{\tbinom {m}{n}}=0

SOLUTION

 

SUMMARY

emmm

REFERENCE

垃圾CSDN

  1. https://blog.csdn.net/a27038/article/details/77129556
  2. https://blog.csdn.net/xieshimao/article/details/6688618
  3. https://blog.csdn.net/xh_reventon/article/details/8690691
  4. https://blog.csdn.net/V5ZSQ/article/details/52021261

CC BY-NC-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

评论

还没有任何评论,你来说两句吧