热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

数论day1——基础知识(们)

[pixiv]https:www.pixiv.netmember_illust.php?modemedium&illust_id61632537向大(hei

这里写图片描述
[pixiv] https://www.pixiv.net/member_illust.php?mode=medium&illust_id=61632537
向大(hei)佬(e)势力学(di)习(tou)

这已经是第二次系统的学数论了,idy学长讲的好清晰。学得糊怪我。

1 一元一次同余方程
2 二元一次不定方程
3 欧拉定理
4 逆元
5 中国剩余定理
6 Lucas 定理
7 容斥原理
8 卡特兰数
9 各种组合数求法
10 积性函数
11 线性筛

1一元一次同余方程

如何解形如 ax≡b(mod m)的方程
其实,同余方程可以写成另一种形式 ax+mt=b(t为某整数),这样一来就有两个未知数了,用下面的二元一次不定方程解出x即可
然而,还有一种做法
分类讨论
1 gcd(a,m)==1 可以求出在模m意义下a的逆元,两边都乘上逆元即可
2 gcd(a,m)!=1
(1)gcd(a,m)-|b 无解
(2)gcd(a,m)|b 方程每个项都除gcd(包括m),然后执行1步骤

2二元一次不定方程

当我们要解整数方程 ax+by=c
根据拓展欧几里得可知 总有x,y满足 ax+by=gcd(a,b),我们希望由此方程*c/gcd(a,b)得出解
令d=gcd(a,b)
1 d-|c 无解,因为无法乘上一个整数
2 d|c 用拓展欧几里得解出x0,y0,再乘上c/d(当然,其中的x0,y0是多解)

3欧拉定理

欧拉函数定义:
phi(n)=|{i∈[1,n]|gcd(i,n)=1}|
即[1,n]中与n互质的数的个数(模n的缩系的大小)
其中有一些性质
1 phi(nm)=phi(n)*phi(m) (gcd(m,n)=1)积性函数
2 phi(n)=n ∏(p|n) (1-1/p) 用于手算
3 n= ∑d|n phi(d) 在一些题目中可以将n化为此形式,会有特殊效果

欧拉定理
if gcd(a,n)=1 , then a^phi(n) ≡ 1 (mod n)
这个定理一般用来求逆元或对指数取膜*(在模意义下,如果指数太大,可以对指数mod phi)
对我来说,这个性质在day2的离散对数和原根有用

欧拉定理还有一个比较有用的扩展
if q>=phi(n) , then a^q≡a^(q mod phi(n)+phi(n)) (mod n)
这样就不需要a与n互质了(然而见识短浅的我并不明白有什么用T_T)

4逆元

在模m意义下,如果gcd(a,m)=1,设b,使得b满足 ab≡1(mod m),则称b为a在模m的逆元
有两种方式求逆元
1 由欧拉定理得,因为gcd(a,m)=1,所以a^(phi(m)-1) *a ≡1(mod m),则a^(phi(m)-1)即为a的逆元。
2 ab≡1(mod m) 可以写成 ab+mt=1的形式,其中b,t是未知数,可以由拓展欧几里得解出b来

这两种方法都二斤八两,一个快速幂带log,一个exgcd带log,不过exgcd通常还是要快点吧?

5中国剩余定理(孙子定理)

(怕还是需要一点篇幅哦,要证明的话)
对于同余方程组 x≡ai (mod mi) (#)
若mi两两互素,设M=∏mi,Mi=M/mi,Ri=Mi^-1(在模mi的意义下的逆元),于是有下面的公式:
x≡∑ai Mi Ri (mod M)(@)
为什么是正确的呢?(这是我为数不多理解原因的定理了。。)
明确一点,只要(@)满足(#),(@)就是正确的
那么,当∑ai Mi Ri 模mi时,Mj(j!=i)必定包含mi,会被模成0,对答案就没有贡献了。Mi虽包含mi,它乘了一个逆元Ri,就为1了,结果方程(@)化简下来就是(#)了

然而两两互素的要求太严格了,有些时候不适用,如果不互素的话。。
可以两两合并
x≡a1(mod m1) ⇒ x=a1+m1*t1
x≡a2(mod m2) ⇒ x=a2+m2*t2
合并后,a1+m1*t1=a2+m2*t2 ,移项后 m1*t1+m2*t2=a2-a1(t是未知数,符号无所谓)即可用扩展欧几里得来求解t1,t2
设d=gcd(m1,m2)
1 d-|a2-a1 ,无解
2 d|a2-a1,解得k1=k10*(a2-a1)/d+k*m2/d,即x=a1+(……)m1,化简得合并后的式子为:
x≡a1+k10*(a2-a1)/d*m1 (mod lcm(m1,m2))(记住就好了)
一直合并下去,只要出现无解就无解,合并到最后就可以得出答案了

6Lucas定理

这里写图片描述
其中,如果出现n mod p 卢卡斯定理主要用来求n,m很大,但p是小质数(10^6)的组合数
(证明我是真不会,知道就好了吧……实在要知道大佬们的博客也有讲)

7容斥原理

这里写图片描述
图片很形象对吧,像极了小学奥数题
公式写下来是:
这里写图片描述
鸽巢原理:把n个鸽子塞进n-1个巢中,那么必有一个巢有至少2个鸽子(通常可以用来分析)

8卡特兰数

先放公式
这里写图片描述
常见模型:
1、有n对括号括号序列的方案数
2、在一个n*n的棋盘上从左下角走到右上角,每次只能向右或向上,且不能越过对角线的路径数
3、n个节点的满二叉树种类(每个节点都有两个子节点或没有)
4、……

其实卡特兰数的模型都可以转化成:有2种东西A,B,任何时刻A的数量都大于等于B

那么下面就用模型2来辅助理解加记忆(现推)
直接求困难,就转化为 总数-不合法数
这里写图片描述
不合法的走法必定会经过图中的虚线,其之后的走法可以沿虚线翻折。不合法的方案就是从(0,0)到(3,5)的走法。由组合数我们可以易得一个矩阵的走法数量,相减即可。

所以,遇到有维持一个东西的数量恒大于等于另一个的问题,就可以想到卡特兰数。模型转化能力倒是很需要。

9各种组合数求法

对于不同数据范围的组合数,求法也会不一样,最好全部掌握
1、n<=5000,直接用c(n,m)=c(n-1,m-1)+(n-1,m)【当年的放苹果问题。。】
2、n<=10^6模大质数(超过n),预处理阶乘及其逆元(o(n)),然后直接用c(n,m)=n!/(m!(n-m)!)计算
3、n<=10^18模小质数(不超过10^6),用Lucas定理,转化为上面的问题
4、n<=10^7,模任意数,可以先用线性筛筛出10^7以内的素数,然后对于每个素数,算出其在n!中对应多少次方(o(logn)),然后指数加减,最后取膜。

【在最后放一个用3做的组合数,把2、逆元都包含进去了

10积性函数

f(nm)=f(n)f(m) (gcd(n,m)=1)
常见有用积性函数:
phi(n):欧拉函数
mui(n):Mobius函数值

嘛,对我来说积性就是在求函数的时候可以在线性筛时o(n)求出来

11线性筛

线性筛可以o(n)的时间和空间复杂度内筛出[1,n]之间的所有素数
设一个数a的最小素数因子是p,则保证a只会被a/p筛掉。这保证了它的时间复杂度是o(n)的。
模板要背熟

int prime[N],cntp=0;
bool not_p[N];
void prime(int n){
not_p[1]=1;
for(int i=2;i<=n;i++){
if(!not_p[i])
prime[++cntp]=i;
for(int j=1;j<=cntp&&i*prime[j]<=n;j++){
not_p[i*prime[j]]=1;
if(i%prime[j]) break;
}
}
}

筛积性函数的话就结合其性质穿插到里面就好了

好啦,就是这样啦
总结:
虽然是基础,但也不能忽略,基础牢固了,才可以衍生出更多的东西

最后,放一道考试题(组合数)

最近Mr. Hu 得到了一个宝箱, 但宝箱被上了锁, 需要解决一个问题才能将其打开, 问题是这样的:
你有n 个不同的苹果, 你想从里面选出m 个来, 问方案数, 结果可能很大, 输出模M 后的结果输出, 其中
M 是k 个不同的素数p1; p2; :::; pk 的乘积.
Mr. Hu 一眼就解决了这个问题, 但他知道你们最近才学了这方面的知识, 于是就把这个问题交给了你们.
Input
第1 行,3 个整数n m k, 意义如上。
第2 行k 个不同的素数:p1 p2 ::: pk.
Output
输出一个整数表示答案.
Sample
treasure.in treasure.out
9 5 2
3 5
6
Note
• 对于10% 的数据,1  n  103,k = 1;
• 对于30% 的数据,1  n  105,k = 1,n • 对于60% 的数据,1  n  1018,k = 1;
• 对于100% 的数据,1  n  1018, 1  k  10
• 对于所有数据,0  m  n  1018, 2  pi  105 且pi 互不相同.

#include
#include
#include
#define ll long long
using namespace std;

const ll N=100000+5;

ll n,m,k,p[20],M=1,mod;
ll jiec[N],niy[N];
ll ans[N],fans=0;

ll mult(ll a,ll b){
ll rt=0;
for(ll i=b;i>0;i>>=1,a=(a+a)%mod)
if(i&1) rt=(rt+a)%mod;
return rt;
}
void exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1,y=0;
}else{
ll x0,y0;
exgcd(b,a%b,x0,y0);
x=y0;
y=x0-(a/b)*y0;
}
}
ll get_niy(ll a){
ll x,y;
exgcd(a,mod,x,y);
x=((x%mod)+mod)%mod;
return x;
}
void init(){
jiec[1]=1;
niy[1]=1;
for(ll i=2;i<=N;i++){
jiec[i]=(jiec[i-1]*i)%mod;
niy[i]=get_niy(jiec[i])%mod;
}
}
ll getans(ll a,ll b){
return mult((mult(jiec[a],niy[b])%mod),niy[a-b])%mod;
}
ll lucas(ll a,ll b){
if(a==b||b==0) return 1;
if(areturn 0;
if(a<mod&&b<mod) return (getans(a,b))%mod;
return mult(lucas(a/mod,b/mod),lucas(a%mod,b%mod))%mod;
}
int main(){
freopen("treasure.in","r",stdin);
freopen("treasure.out","w",stdout);
scanf("%I64d%I64d%I64d",&n,&m,&k);
for(ll i=1;i<=k;i++){
scanf("%I64d",&p[i]);
M*=p[i];
}
for(ll i=1;i<=k;i++){
mod=p[i];
init();
ans[i]=lucas(n,m);
}
for(ll i=1;i<=k;i++){
mod=p[i];
ll orz=M/p[i],ni_orz=get_niy(orz)%mod;
mod=M;
fans=(fans+mult((mult(orz,ni_orz)%M),ans[i])%M)%M;
}
printf("%I64d\n",fans);
return 0;
}

推荐阅读
  • 问题描述现在,不管开发一个多大的系统(至少我现在的部门是这样的),都会带一个日志功能;在实际开发过程中 ... [详细]
  • 来自FallDream的博客,未经允许,请勿转载,谢谢。一天一套noi简直了.昨天勉强做完了noi2011今天教练又丢出来一套noi ... [详细]
  • 探索CNN的可视化技术
    神经网络的可视化在理论学习与实践应用中扮演着至关重要的角色。本文深入探讨了三种有效的CNN(卷积神经网络)可视化方法,旨在帮助读者更好地理解和优化模型。 ... [详细]
  • 探讨多种方法来确定Java对象的实际类型,包括使用instanceof关键字、getClass()方法等。 ... [详细]
  • HDU 2537 键盘输入处理
    题目描述了一个名叫Pirates的男孩想要开发一款键盘输入软件,遇到了大小写字母判断的问题。本文提供了该问题的解决方案及实现方法。 ... [详细]
  • 本文详细介绍了如何在PHP中使用Memcached进行数据缓存,包括服务器连接、数据操作、高级功能等。 ... [详细]
  • 在学习了Splay树的基本查找功能后,可能会觉得它与普通的二叉查找树没有太大的区别,仅仅是通过splay操作减少了时间开销。然而,Splay树之所以被誉为“序列之王”,主要在于其强大的区间操作能力。 ... [详细]
  • 本文探讨了如何选择一个合适的序列化版本ID(serialVersionUID),包括使用生成器还是简单的整数,以及在不同情况下应如何处理序列化版本ID。 ... [详细]
  • 本文总结了 #define 在 C/C++ 编程中的多种用途和技巧,包括定义常量、函数、宏以及条件编译等,并提供了详细的示例和注意事项。 ... [详细]
  • 本文介绍了如何使用 Python 的 Pyglet 库加载并显示图像。Pyglet 是一个用于开发图形用户界面应用的强大工具,特别适用于游戏和多媒体项目。 ... [详细]
  • 视觉Transformer综述
    本文综述了视觉Transformer在计算机视觉领域的应用,从原始Transformer出发,详细介绍了其在图像分类、目标检测和图像分割等任务中的最新进展。文章不仅涵盖了基础的Transformer架构,还深入探讨了各类增强版Transformer模型的设计思路和技术细节。 ... [详细]
  • D17:C#设计模式之十六观察者模式(Observer Pattern)【行为型】
    一、引言今天是2017年11月份的最后一天,也就是2017年11月30日,利用今天再写一个模式,争取下个月(也就是12月份& ... [详细]
  • 本文探讨了如何将个人经历,特别是非传统的职业路径,转化为职业生涯中的优势。通过作者的亲身经历,展示了舞蹈生涯对商业思维的影响。 ... [详细]
  • 题面:P3178[HAOI2015]树上操作好像其他人都嫌这道题太容易了懒得讲,好吧那我讲。题解:第一个操作和第二个操作本质上是一样的&# ... [详细]
  • 汇总了2023年7月7日最新的网络安全新闻和技术更新,包括最新的漏洞披露、工具发布及安全事件。 ... [详细]
author-avatar
凤凰花开清风自来_406
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有