ACM 数论基础

一、从取模开始

定义1.1

若(a-b)可以被m整除，即(a-b)%m == 0 则称其a与b对m同余，记做

栗子:

(20-10) / 2 = 5  即20与10 对 2 同余，记做

定理1.1

同余的基本性质

（分别有+-*/四条，暂略）

素数线性筛（欧拉筛）

const int maxn = 1e8 + 10;
int prime[maxn];
bool vis[maxn];
int cnt = 0;
//inline int read() {
//
int x = 0;int f = 1; char c = getchar();
//
while(c<'0' || c>'9') {if(c=='-') f = -f; c = getchar();}
//
while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
//
return x*f;
//}
void Euler(int n) {
for(int i = 2; i <= n; i++) {
if(!vis[i]) prime[++cnt] = i;
for(int j = 1; j <= cnt && i * prime[j] <= n; j++) {
vis[i*prime[j]] = 1;
if(i%prime[j] == 0) break;
}
}
return;
}

二、唯一分解定理

一个数可以被分解成若干个素数幂积乘积。

基于此可以延伸得到：

数A的所有因子个数（即a1..an的N个数）

求出所有因子之和

(此公式可以使用等比数列求和化简，？好像不行）

三、逆元

拓展欧几里得

ll a, b, x, y, k;
void exgcd(ll a, ll b){
if(b == 0) {
x = 1;
y = 0;
return;
}
exgcd(b, a%b);
ll tx = x;
x = y;
y = tx - (a/b)*y;
return;
}

最后

以上就是冷傲小丸子为你收集整理的ACM 数论基础的全部内容，希望文章能够帮你解决ACM 数论基础所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。