热门标签 | 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;
}

推荐阅读
  • C++ 开发实战:实用技巧与经验分享
    C++ 开发实战:实用技巧与经验分享 ... [详细]
  • 在Kohana 3框架中,实现最优的即时消息显示方法是许多开发者关注的问题。本文将探讨如何高效、优雅地展示flash消息,包括最佳实践和技术细节,以提升用户体验和代码可维护性。 ... [详细]
  • 单链表的高效遍历及性能优化策略
    本文探讨了单链表的高效遍历方法及其性能优化策略。在单链表的数据结构中,插入操作的时间复杂度为O(n),而遍历操作的时间复杂度为O(n^2)。通过在 `LinkList.h` 和 `main.cpp` 文件中对单链表进行封装,我们实现了创建和销毁功能的优化,提高了单链表的使用效率。此外,文章还介绍了几种常见的优化技术,如缓存节点指针和批量处理,以进一步提升遍历性能。 ... [详细]
  • ButterKnife 是一款用于 Android 开发的注解库,主要用于简化视图和事件绑定。本文详细介绍了 ButterKnife 的基础用法,包括如何通过注解实现字段和方法的绑定,以及在实际项目中的应用示例。此外,文章还提到了截至 2016 年 4 月 29 日,ButterKnife 的最新版本为 8.0.1,为开发者提供了最新的功能和性能优化。 ... [详细]
  • 深入解析 Android 中 EditText 的 getLayoutParams 方法及其代码应用实例 ... [详细]
  • 如何利用Java 5 Executor框架高效构建和管理线程池
    Java 5 引入了 Executor 框架,为开发人员提供了一种高效管理和构建线程池的方法。该框架通过将任务提交与任务执行分离,简化了多线程编程的复杂性。利用 Executor 框架,开发人员可以更灵活地控制线程的创建、分配和管理,从而提高服务器端应用的性能和响应能力。此外,该框架还提供了多种线程池实现,如固定线程池、缓存线程池和单线程池,以适应不同的应用场景和需求。 ... [详细]
  • Squaretest:自动生成功能测试代码的高效插件
    本文将介绍一款名为Squaretest的高效插件,该工具能够自动生成功能测试代码。使用这款插件的主要原因是公司近期加强了代码质量的管控,对各项目进行了严格的单元测试评估。Squaretest不仅提高了测试代码的生成效率,还显著提升了代码的质量和可靠性。 ... [详细]
  • 图论入门基础教程
    图论是计算机科学和数学中的重要分支,本教程旨在为初学者提供全面的基础知识。通过实例解析,如“昂贵的聘礼”问题,讲述了一个年轻探险家在印第安部落与酋长女儿的爱情故事,展示了图论在解决实际问题中的应用。教程内容涵盖了图的基本概念、表示方法以及常见算法,适合各类读者学习。 ... [详细]
  • 在洛谷 P1344 的坏牛奶追踪问题中,第一问要求计算最小割,而第二问则需要找到割边数量最少的最小割。通过为每条边附加一个单位权值,可以在求解最小割时优先选择边数较少的方案,从而同时解决两个问题。这种策略不仅简化了问题的求解过程,还确保了结果的最优性。 ... [详细]
  • 技术日志:使用 Ruby 爬虫抓取拉勾网职位数据并生成词云分析报告
    技术日志:使用 Ruby 爬虫抓取拉勾网职位数据并生成词云分析报告 ... [详细]
  • 微信小程序实现类似微博的无限回复功能,内置云开发数据库支持
    本文详细介绍了如何利用微信小程序实现类似于微博的无限回复功能,并充分利用了微信云开发的数据库支持。文中不仅提供了关键代码片段,还包含了完整的页面代码,方便开发者按需使用。此外,HTML页面中包含了一些示例图片,开发者可以根据个人喜好进行替换。文章还将展示详细的数据库结构设计,帮助读者更好地理解和实现这一功能。 ... [详细]
  • 手指触控|Android电容屏幕驱动调试指南
    手指触控|Android电容屏幕驱动调试指南 ... [详细]
  • 寒假作业解析:第三周 2月12日 第7题
    尽快完成之前的练习任务!每日一练2.1 Problem A Laurenty and Shop 的题目要求是选择两条不同的路线以最小化总的等待时间。简要分析:通过对比不同路线的等待时间,可以找到最优解。此问题可以通过动态规划或贪心算法来解决,具体取决于路线的复杂性和约束条件。 ... [详细]
  • 2018年9月21日,Destoon官方发布了安全更新,修复了一个由用户“索马里的海贼”报告的前端GETShell漏洞。该漏洞存在于20180827版本的某CMS中,攻击者可以通过构造特定的HTTP请求,利用该漏洞在服务器上执行任意代码,从而获得对系统的控制权。此次更新建议所有用户尽快升级至最新版本,以确保系统的安全性。 ... [详细]
  • 深入解析:React与Webpack配置进阶指南(第二部分)
    在本篇进阶指南的第二部分中,我们将继续探讨 React 与 Webpack 的高级配置技巧。通过实际案例,我们将展示如何使用 React 和 Webpack 构建一个简单的 Todo 应用程序,具体包括 `TodoApp.js` 文件中的代码实现,如导入 React 和自定义组件 `TodoList`。此外,我们还将深入讲解 Webpack 配置文件的优化方法,以提升开发效率和应用性能。 ... [详细]
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社区 版权所有