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

初等数论

时间:2023-06-28 12:00:14浏览次数:46  
标签: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......