约数
luckydrawbox
·
·
算法·理论
正约数集合
试除法
求出 N 的正约数集合。
```cpp
int m;
int factor[1600];
void q_factor(int n){
for (int i=1;i*i<=n;i++){
m=0;
if(n%i==0){
factor[++m]=i;
if(i^n/i)
factor[++m]=n/i;
}
}
}
```
$factor_{1\sim m}$ 就是 $N$ 的正约数集合。
### 倍数法
求出 $1\sim N$ 的正约数集合。
$O(N\log N)$。
```cpp
vector<int>factor[500010];
void q_factor(int n){
for(int i=1;i<=n;i++)
for(int j=1;j<=n/i;j++)
factor[i*j].push_back(i);
}
```
$factor_{i,0\sim factor_i.size()-1}$ 就是 $i$ 的正约数集合。
## 最大公约数
### 更相减损术
```cpp
long long gcd(long long a,long long b){
return b?((a%2||b%2)?gcd(b,abs(a-b)):2*gcd(a/2,b/2)):a;
}
```
### 欧几里得算法
$O(log(a+b))$。
```cpp
long long gcd(long long a,long long b){
return b?gcd(b,a%b):a;
}
```
## 最小公倍数
```cpp
long long lcm(long long a,long long b){
return a/gcd(a,b)*b;
}
```
## 欧拉函数
### 求某个数的欧拉函数
$O(\sqrt N)$。
```cpp
long long phi(long long n){
long long ans=n;
for(long long i=2;i*i<=n;i++)
if(n%i==0){
ans=ans/i*(i-1);
while(n%i==0)
n/=i;
}
if(n>1)
ans=ans/n*(n-1);
return ans;
}
```
### 利用 Eratosthenes 筛法求 $2\sim N$ 的欧拉函数
$O(N\log N)$。
```cpp
int phi[N];
void euler(int n){
for(int i=2;i<=n;i++)
phi[i]=i;
for(int i=2;i<=n;i++)
if(phi[i]==i)
for(int j=i;j<=n;j+=i)
phi[j]=phi[j]/i*(i-1);
}
```
### 利用线性筛法优化求 $2\sim N$ 的欧拉函数
$O(N)$。
```cpp
int m;
int v[N],prime[N],phi[N];
void euler(int n){
memset(v,0,sizeof(v));
m=0;
for(int i=2;i<=n;i++){
if(!v[i]){
v[i]=prime[++m]=i;
phi[i]=i-1;
}
for(int j=1;j<=m;j++){
if(prime[j]>v[i]||prime[j]>n/i)
break;
v[i*prime[j]]=prime[j];
phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
}
}
}
```
[back](https://www.luogu.com.cn/article/dltjrzaa)