type
status
date
slug
summary
tags
category
icon
password
comment
快速幂
快速求
扩展欧几里得定理
题目中经常需要求二元一次方程的解
设方程,则可求得最大公约数,和方程的解
有解的条件是c必须为最大公约数d的倍数
满足上述条件可求得方程的解:
注意python和c++采用了两种代码,python给出了x和y的返回值,不用传参;c++传入了参数地址,可直接修改传入变量,不用返回。
逆元
- 为素数情况下用费马小定理
→ a关于p的逆元为
- 通常情况
a关于b的逆元,即的解x,同时是小于b的正整数
中国剩余定理
有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?
这是中国古代的数学问题,如何求一元同余线性方程?
线性筛
上述代码为一个简单的线性筛模板,许多数和质因子有关,下面为利用线性筛求素数p,欧拉函数phi,莫比乌斯函数mu,约数个数d,约数和f等
- Author:E1ainay
- URL:https://e1ainay.top/article/alogrithmwiki/shulun
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts