首页 > 其他分享 >初等数论

初等数论

时间：2023-06-28 12:00:14浏览次数：45  
标签：gcd 数论 ll varphi times pmod 初等 equiv

初等数论

\(\mathcal{P}art\) 1.基础概念

  • 整除

对两个正整数 \(a\)，\(b\)（\(b\le a\)），如果存在一个整数 \(k\) 使得 \(a=kb\)，则称 \(b\) 整除 \(a\)，记作 \(b|a\)

  • 带余除法

对任何整数 \(a\) 和正整数 \(b\)，一定存在一个整数 \(r\in[0,b)\) 和一个整数 \(k\)，使得 \(a=kb+r\)，称上式为 \(a\) 和 \(b\) 的带余除法式， \(r\) 称为 \(a\) 除以 \(b\) 的余数

  • 因数

对一个正整数 \(x\)，所有能整除 \(x\) 的正整数均为 \(x\) 的因子

  • 公因数

两个正整数 \(x,y\) 共有的因数称为它们的公因数

  • 质数

因数只有 \(1\) 和自身的正整数叫做质数；\(1\) 不是质数

  • 质因子

对 \(x\) 的因数中是质数的那部分被称为质因子

  • 算数基本定理

对任何一个大于 \(1\) 的整数 \(x\)，\(x\) 均能表示成若干个 \(x\) 的质因子的乘积。这个表示法是唯一的

\(\mathcal{P}art\) 2.基础算法

  • 因数分解

\(\mathcal{O}(\sqrt{x})\) 对任意正整数 \(x\) 分解因子

  • 埃氏筛：

\(\mathcal{O(\log{\log{n}})}\) 的筛出 \(n\) 以内的质数

  • 质因子分解

\(\mathcal{O}(\sqrt{x})\) 对任意正整数 \(x\) 分解质因子

证明不可能会有两个大于 \(\sqrt{x}\) 的数

易证

  • 欧几里得算法

\(\gcd(a,b)=\gcd(b,a\bmod b)\)

\(\mathcal{Part}\) 3.线性筛

先给出代码

void getPrime(const int N = 100000000) {
	for (int i = 2; i <= N; ++i) {
		if (!np.test(i)) {
			prm.push_back(i);
		}
		for (auto j : prm) 
            if (i * j <= N) {
				int k = i * j;
				np.set(k);
				if (i % j == 0) break;
			} else break;
	}
}

上述代码的时间复杂度为 \(\mathcal{O}(n)\)

  • 正确性证明：

我们设一个合数 \(x\)，使得 \(x=py,p\in \mathbb{P}\)，且 \(p\) 为最小的

\(p\) 为最小的，则 \(y\) 的因子里没有比 \(p\) 小的

则一定会枚举到 \(i=y\)，\(j=p\) 的情况，则 \(x\) 一定会被筛掉

  • 线性证明：

想要是线性，则要证明每个合数只会被筛一遍

我们设一个合数 \(x\)，使得 \(x=py=qz\) 满足 \(p,q\in\mathbb{P},\gcd(p,q)=1,p<q\)

则 \(p\) 一定是 \(z\) 的因子

所以当 \(i=z,j=p\) 时就会退出，就会导 致 \(x\) 只会被筛一遍

证毕

  • 性质

因为 \(x\) 只会被它最小筛掉，所以可求一个数的最小质因子

\(\mathcal{Part}\) 4.不定方程

  • 定义

形如 \(ax+by=c\)，其中 \(a,b,c\) 是已知数的方程叫做二元一次不定方程

  • 引理

方程 \(ax+by=c\) 有解当且仅当 \(\gcd(a,b)|c\)

证明：

记住就行

  • 求解 (exgcd进行求解)

因为 \(\gcd(a,b)|c\)，所以我们设 \(\cfrac{c}{\gcd(a,b)}=k,k\in \mathbb{N^*}\)

因此我们只需要求 \(ax+by=\gcd(a,b)\) 即可，最后 \(x,y\) 同乘 \(k\) 即可

\[ax+by=\gcd(a,b)=\gcd(b,a\bmod b)=bx'+(a\bmod b)y'=bx'+(a-\lfloor \cfrac{a}{b}\rfloor\times b)y' \]

接下来给等式左右边做个系数对应，即

\[ax+by=ay'+b(x'-\lfloor \cfrac{a}{b} \rfloor y') \]

所以递归求解后答案是

\[\begin{cases} x=y'\\ y=x'-\lfloor \cfrac{a}{b} \rfloor y' \end{cases} \]

  • 边界

显然，最后的边界是 \(b=0\)，考虑前面的一个式子

显然 \(b|a\)，方程为

\[ax''''+by''''=b \]

显然有解

\[\begin{cases} x''''=0\\ y''''=1 \end{cases} \]

即解决

  • 代码
void Ex_gcd(const ll a, const ll b, ll &X, ll &Y) {
	if (a % b == 0) {
		X = 0; Y = 1;
	} else {
		Ex_gcd(b, a % b, Y, X);
		Y ‐= a / b * X;
	}
}

\(\mathcal{Part}\) 5.同余方程

  • 定义

对两个整数 \(a,b\) 如果他们除以 \(d\) 的余数相同，则称它们模 \(d\) 同余，记作 \(a\equiv b\pmod d\)

  • 性质

在同余号两侧同时加、减、乘任何整数，同余式仍成立

显然，\(a,b,r\) 的带余除法表达式等价为 \(a\equiv r\pmod b\)

\(\mathcal{Part}\) 6.威尔逊定理

正整数 \(p\) 是质数的充分必要条件是 \((p-1)! \equiv -1\pmod p\)

啥用没有，记住就行

\(\mathcal{Part}\) 7.欧拉函数

  • 定义

定义欧拉函数 \(\varphi(n)\) 表示小于等于 \(n\) 的数中与 \(n\) 互质的数的个数。特别的，\(\varphi(1)=1\)

显然，\(\varphi(p)=p-1,p\in \mathbb{P}\)

  • 性质

  1. 积性：如果 \(\gcd(a,b)=1\) 则 \(\varphi(a\times b)=\varphi(a)\times \varphi(b)\)

  2. 欧拉反演：\(\sum_{d|n}\varphi(d)=n\)

  3. 性质三：对任何质数 \(p\)，\(\varphi(p^k)=p^k-p^{k-1}\)

证明：

\(p^k\) 个数中，有 \(p^{k-1}\) 个数跟 \(p^k\) 不互质，即 \(1p,2p…p^{k-1}p\)

即证

  • 计算
  1. 单个欧拉函数：

设 \(n\) 的唯一分解式为 \(n=p_1^{k_1}…p_s^{k_s}\) 根据积性，\(\varphi(n)=\prod_{i=1}^s \varphi(p_i^{k_i})=\prod_{i=1}^{s}p^{k_i}-p^{k_i-1}\)

  1. 线性筛欧拉函数：

在线性筛的同时求出欧拉函数，设 \(k\) 的最小质因子为 \(j\)，则 \(i=\cfrac{k}{j}\)

分三种情况讨论

  • \(k\) 为质数时，明显的 \(\varphi(k)=k-1\)
  • \(i\) 和 \(j\) 互质时，根据积性，\(\varphi(k)=\varphi(i) \times \varphi(j)\)
  • \(j|i\) 时，\(\varphi(k)=j\times \varphi(i)\)，推导如下：

设 \(k=j^q\times p\)，其中 \(p\) 不含 \(k\) 的最小质因子，则：

\[\begin{aligned} \varphi(k)&=\varphi(j^q)\times \varphi(p)\\ &=(j^{q}-j^{q-1})\times \varphi(p)\\ &=j(j^{p-1}-j^{p-2})\times \varphi(p)\\ &=j\times\varphi(j^{p-1}) \times \varphi(p)\\ &=j\times\varphi(i) \end{aligned} \]

即证

\(\mathcal{Part}\) 8. 逆元

我们不能再同余符号两边除以一个数，但是我们需要进行这样的操作怎么办？

这时候引出逆元

定义 \(x^{-1}\) 满足 \(xx^{-1}\equiv 1 \pmod{p}\)，这个时候就做到了除法的感觉

  • 性质
  1. 逆元存在性定理：当 \(x\) 在模 \(p\) 同余下有逆元当且仅当 \(\gcd(x,p)=1\)，\(0\) 没有逆元
  2. 逆元唯一性定理：模 \(p\) 同余下，一个整数 \(x\) 的逆元若存在，则唯一，注意这里的逆元是在 \([1,p)\) 之间的
  3. 一个数的逆元的逆元等于它本身
  • 计算
  1. exgcd求解

对于给定的 \(x,p\)，显然 \(x\times x^{-1} \equiv 1\pmod{p}\)，把它改成带余除法式即为

\(x\times x^{-1}=kp+1\)，改下顺序，注意这里 \(k\) 是系数，正负号没要求，即为

\(x\times x^{-1}+pk=1\)，由不定方程存在性定理可得 \(\gcd(x,p)|1\)，根据逆元存在性定理可以得到这个不定方程是有解的

用exgcd求解即可

  1. 这里介绍欧拉定理和费马小定理

欧拉定理：对于任意正整数 \(a,m\) 且 \(\gcd(a,m)=1\)，一定有：\(a^{\varphi(m)}\equiv 1\pmod{m}\)，当 \(m\) 为质数时，由 \(\varphi(m)=m-1\)，此定理退化为：

费马小定理：对任意正整数 \(a\) 和任意质数 \(p\)，有 \(a^{p-1}\equiv 1 \pmod{p}\)

  1. 费马小定理求解

根据费马小定理，\(a^{p-1}\equiv 1\pmod{p}\)，两侧同乘 \(a^{-1}\) 得到 \(a^{-1}\equiv a^{p-2} \pmod{p}\)

于是得到了逆元的你一种求法：快速幂求出 \(a^{p-2}\bmod p\) 即可

注意这里 \(p\) 为质数，常用的质数为：

\[\begin{aligned} 1145141\\ 19260817\\ 10^9+7\\ 10^7+7\\ 998,244,353 \end{aligned} \]

一定要记住

  1. 线性筛逆元

令 \(inv_i\) 为 \(i\) 在模 \(p\) 意义下的逆元，则：

\[inv_i\equiv -\lfloor\cfrac{p}{i} \rfloor \times inv_{p \ \bmod \ i}\pmod{p} \]

证明：

写出 \(i\) 在模 \(p\) 意义下的带余除法式为：\(p=ki+r\)，两边对 \(p\) 取余，得到

\(ki+r\equiv 0\pmod{p}\)

移项：\(r\equiv-ki\pmod{p}\)

同乘 \(i^{-1}r^{-1}\)，得 \(i^{-1}\equiv -kr^{-1}\pmod{p}\)

注意到：\(k=\lfloor\cfrac{p}{i} \rfloor\)，\(r=p\bmod i\)，即证

Inv[1] = 1;
	for (int i = 2; i <= n; i ++) 
		Inv[i] = (p - p / i) * Inv[p % i] % p;//这里避免他是负数
  • 组合数逆元
  1. 正推：

显然，我们要预处理出 \((x!)^{-1}\)

我们先预处理出 \(x^{-1}\)，显然 \((x!)^{-1}=((x-1)!) ^{-1}\times x^{-1}\)

这种方式要预处理出 \(x^{-1}\) 效率很低，我们考虑另一种方法

  1. 逆推

直接用费马小定理求出 \((n!)^{-1}\)，然后根据 \((i!)^{-1}=((i+1)!)^{-1} \times i\)，反着地推回去即可

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MAXN = 5e6 + 7, Mod = 998244353;

int T, N;

ll F[MAXN], Inv[MAXN];

ll qpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % Mod;
		a = a * a % Mod, b >>= 1;
	}
	return ans;
}

int main () {
	ios :: sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> T >> N;
	F[0] = 1;
	for (int i = 1; i <= N; i ++) F[i] = F[i - 1] * i % Mod;
	Inv[N] = qpow(F[N], Mod - 2);
	for (int i = N - 1; i >= 0; i --) Inv[i] = Inv[i + 1] * (i + 1) % Mod;
	ll ans = 0;
	while (T --) {
		ll a, b;
		cin >> a >> b;
		ans ^= (F[a] * Inv[b] % Mod * Inv[a - b] % Mod);
	}
	cout << ans << '\n';
 	return 0;
}

\(\mathcal{Part}\) 9.中国剩余定理(CRT)

现在我们要解出一个同余方程组形如：

\[\begin{cases} x \equiv a_1 \pmod{m_1}\\ x \equiv a_2 \pmod{m_2}\\ x \equiv a_3 \pmod{m_3}\\ \cdots \ \cdots\ \cdots\ \cdots \end{cases} \]

其中保证 \(m_i\) 两两互质，求 \(x\) 的通解

  • \(\mathcal{Solution}\)

我们转换下题意，也就是我们要求一个 \(S\) 使得其：

\[x \equiv S \equiv a_i \pmod{m_i} \]

现在我们尝试构造 \(S\)

规定 \(M=\prod m_i\)，\(M_i=\cfrac{M}{m_i}\)，\(t_i\) 是在模 \(m_i\) 下 \(M_i\) 的逆元

我们根据 \(x \equiv a_i \pmod{m_i}\) 和 \(t_i M_i \equiv 1\pmod{m_i}\)，两边同乘1可得：

\(x\equiv a_iM_it_i \pmod{m_i}\)

现在我们令 \(j\ne i\)，则有 \(M_j\equiv 0\pmod{m_i}\)，两边同乘得到：\(a_jM_jt_j\equiv 0\pmod{m_i}\)

我们将原式加上0可以得到：\(x\equiv a_iM_it_i+a_jM_jt_j\pmod{m_i}\)

我们将所有 \(j\) 都加起来，可以得到 \(x\equiv \sum a_iM_it_i \pmod{m_i}\)

我们发现 \(\sum a_iM_it_i\) 是个定值，设其为 \(S\)

于是我们现在就满足 \(x\equiv S \pmod {m_i}\)

现在只需要证明 \(S\equiv a_i \pmod{m_i}\) 即可

很容易发现 \(t_iM_i\) 在模 \(m_i\) 下为 1 的，即证明了

根据简单的推导，可以得到通解为：

\(S+Mk(k\in \mathbb{N+})\)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 27;

int n;

ll A[MAXN], B[MAXN], ans, M[MAXN], m = 1;

void Ex_gcd(const ll a, const ll b, ll &X, ll &Y) {
	if (a % b == 0) {
		X = 0; Y = 1;
	} else {
		Ex_gcd(b, a % b, Y, X);
		Y -= a / b * X;
	}
}

int main () {
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> A[i] >> B[i];
		m = m * A[i]; }
	for (int i = 1; i <= n; i ++) {
		M[i] = m / A[i];
		ll x = 0, y = 0;
		Ex_gcd(M[i], A[i], x, y); x = (x + A[i]) % A[i];
		ans += B[i] * M[i] * x; ans %= m;
	}
	cout << ans << '\n';
	return 0;
}

\(\mathcal{Part}\) 10. 尾声

数论还有很多定理等着你去了解

标签：gcd,数论,ll,varphi,times,pmod,初等,equiv
From： https://www.cnblogs.com/Phrvth/p/17511037.html

相关文章

  • Dreaming of Freedom(数论,贪心)
    用nsqrt(n)的时间复杂度就能过//DreamingofFreedom:https://codeforces.com/problemset/problem/1826/C#include<bits/stdc++.h>//#defineintlonglongusingnamespacestd;constintN=1e5+10,mod=1e9+7;strings;intn,t,a[N],f[N],res,num,ans,m;boolvis[N];i......
  • 数论
    类欧几里德\(\text{令}\spacef(a,b,c,n)=\sum_{i=1}^n\lfloor\frac{ai+b}{c}\rfloor\)\(f(a,b,c,n)=\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor+f(a\%c,b\%c,c,n)\)第二类斯特林数求自然幂和$\sum_{i=1}^ni^k=\sum_{i=1}^n\sum_{......
  • Add Modulo 10(数论,思维,数学,规律)
    思路：找规律情况一:尾数为5或0为5时进行一次操作变成0的情况。而尾数是 0 时操作无意义，所有数必须相等。情况二：尾数为 1,3,7,9可进行一次操作变成情况三。情况三：尾数为 2,4,6,8我们通过找规律发现：2⇒4⇒8⇒16⇒224⇒8⇒16⇒22⇒246⇒12⇒14⇒18⇒268⇒16⇒22⇒24⇒28......
  • 【蓝桥杯_真题演练】第九届C/C++省赛B组_C-乘积尾零（C++_数论）
    Problem如下的10行数据，每行有10个整数，请你求出它们的乘积的末尾有多少个零？56504542355447394641143871907390432927587949611356595245743230514434670435949937117368663397475975573070228714539899148657223135117040145510512072928809......
  • 【蓝桥杯_真题演练】第十届C/C++省赛B组_H-等差数列（C++_gcd_数论）
    ProblemProcess在输入的时候先去重，然后进行排序，至于他们的公差p则需要计算每两个相邻数值之间差值的最大公因数，最终的结果应该是Code#include<bits/stdc++.h>usingnamespacestd;#definelllonglongintn,a[100010],cnt;set<int>s;intgcd(inta,intb){ returnb==......
  • P1062 数列(C++_数论)
    题目描述给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：（该序列实际上就是：)请你求出这个序列的第N项的值（用10进制数表示）。例如，对于k=3，N=100，正确答案应该是981。输入格式2个正整数，用一个空格隔开：输出格式1个正整......
  • P1582 倒水（C++_数论_进制）
    题目描述一天，CC买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着~~CC发现瓶子实在太多了，于是他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子，把一个瓶子的水全部倒进另一个里，然后把空瓶丢弃。(不能丢弃有水的瓶子)显然在某些情况下CC无法达到目标，比......
  • PTA_乙级_1001 害死人不偿命的(3n+1)猜想 (C++_数论)
    卡拉兹(Callatz)猜想：对任何一个正整数n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把(3n+1)砍掉一半。这样一直反复砍下去，最后一定在某一步得到n=1。卡拉兹在1950年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹......
  • 十一届蓝桥杯研究生组国赛-循环小数(数论)
    十一届蓝桥杯研究生组国赛-循环小数1、题目描述2、解题思路3、代码实现1、题目描述  已知S是一个小于11的循环小数，请计算与S相等的最简真分数是多少。  例如0.3333⋯0.3333⋯等于1331，0.1666⋯0.1666⋯等于1661。输入描述  输入第一行包含两个整数p和q，表示......
  • [数论]取模
    Mod一、longlong乘法取模核心思想用longdouble估计商的取值，然后任它溢出,它的真实答案和它%\(2^{64}\)次方答案是一样的\(x*y\)%\(m=x*y-\dfrac{x*y}{m}*m\)代码llmul(llx,lly,llm){ x%=m;y%=m; lld=((longdouble)x*y/m); d=x*y-d*m; if(d>=m)d-=m; i......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99