数学知识
数论
一些重要性质
1. d|n --> (n/d)|n。d|n–>d能整除n。
所以约数总是成对出现的。
2. d|a && d|b --> d|ax+by
质数
在大于1的整数中，只包含1和本身两个约数，就被看成是质数或者叫素数。
质数判定
试除法O(srqt(N))
bool is_prime( LL x ){
if( x < 2 ) return false;
for( int i = 2 ; i <= x/i ; i++ )
if( x%i == 0 ) return false;
return true;
}
分解质因数
试除法O(sqrt(N))
从小到大，尝试n的所有的因数。因为约数成对出现，
// 输出每个质因数的底数和指数
void divide( int n ){
for( int i = 2 ; i <= n/i ; i++ ){
if( n%i == 0 ){// i一定是质因数
int s = 0;
while( n%i == 0 ){
n /= i;
s++;// i 在n中出现的次数
}
cout << i << ' ' << s << endl;
}
}
if( n > 1 ) cout << n << ' ' << 1 << endl;
cout << endl;
}
筛质数
朴素版O(nlogn)
每次筛掉数k的倍数
int cnt,primes[1000010];
bool st[1000010];
void get_primes( int n ){
for( int i = 2 ; i <= n ; i++ ){
if( !st[i] ) primes[++cnt] = i;
for( int j = i+i ; j <= n ; j += i ) st[j] = 1;
}
cout << cnt ;
}
优化版O(nloglogn)
埃氏筛法
每次筛掉质数的倍数
bool st[N];
int cnt , prime[N];
void get_primes( int n ){
for( int i = 2 ; i <= n ; i++ )
if( !st[i] ){
prime[++cnt] = i;
for( int j = i+i ; j <= n ; j+=i ) st[ j ] = 1;
}
cout << cnt;
}
线性筛法
从小到大枚举质数，每次把质数的乘积筛掉。
当i%primes[j] == 0这句话成立的时候，primes[j]一定是primes[j]*i的最小质因子。
当i%primes[j] != 0这句话成立的时候，primes[j]一定小于i的所有质因子，primes[j]一定是primes[j]*i的最小质因子。
void get_primes( int n ){
for( int i = 2 ; i <= n ; i++ )
{
if( !st[i] ) primes[cnt++] = i;
for( int j = 0 ; primes[j] <= n/i ; j++ )
{
st[ primes[j]*i ] = true;
if( i%primes[j] == 0 ) break;
}
}
cout << cnt;
}
(1).若n在10的6次方的话,线性筛和埃氏筛的时间效率差不多,若n在10的7次方的话,线性筛会比埃氏筛快了大概一倍.
(2).思考:一:线性筛法为什么是线性的?
二:线性筛法的原理是什么?
(3).核心:1~n内的合数p只会被其最小质因子筛掉.
(4).原理:1~n之内的任何一个合数一定会被筛掉,而且筛的时候只用最小质因子来筛,
然后每一个数都只有一个最小质因子,因此每个数都只会被筛一次,因此线性筛法是线性的.
(5).枚举到i的最小质因子的时候就会停下来,即”if(i%primes[j]==0) break;”.
(6).因为从小到大枚举的所有质数,所以当”i%primes[j]!=0”时,primes[j]一定小于i的最小质因子,
primes[j]一定是primes[j]i的最小质因子.
(7).因为是从小到大枚举的所有质数,所以当”i%primes[j]==0”时,primes[j]一定是i的最小质因子,
而primes[j]又是primes[j]的最小质因子,因此primes[j]是iprimes[j]的最小质因子.
(8).关于for循环的解释:
注:首先要把握住一个重点:我们枚举的时候是从小到大枚举的所有质数
1.当i%primes[j]==0时,因为是从小到大枚举的所有质数,所以primes[j]就是i的最小质因子,而primes[j]又是其本身
primes[j]的最小质因子,因此当i%primes[j]==0时,primes[j]是primes[j]i的最小质因子.
2.当i%primes[j]!=0时,因为是从小到大枚举的所有质数,且此时并没有出现过有质数满足i%primes[j]==0,
因此此时的primes[j]一定小于i的最小质因子,而primes[j]又是其本身primes[j]的最小质因子,
所以当i%primes[j]!=0时,primes[j]也是primes[j]i的最小质因子.
3.综合1,2得知,在内层for循环里面无论何时,primes[j]都是primes[j]i的最小质因子,因此”st[primes[j]i]=true”
语句就是用primes[j]i这个数的最小质因子来筛掉这个数.
约数
试除法判断约数
vector<int> get_dis( int x ){
vector<int> res;
for( int i = 1 ; i <= x/i ; i++ ){
if( x%i == 0 ){// i一定是约数
res.push_back( i );
if( i != x/i ) res.push_back( x/i );
}
}
sort( res.begin() , res.end() );
return res;
}
约数个数
$ N = {p_1}^{a_1} * {p_2}^{a_2} * ..... * {p_k}^{a_k} $ ，N分解质因数后的形式
$ d = {p_1}^{b_1} * {p_2}^{b_2} * ..... * {p_k}^{b_k} $ ，d是N的约数
约数个数 =
$ (a_1+1)*(a_2+1)*…*(a_k+1) $
$ b_1 … b_k $的选法个数就是约数个数 $ 0 <= b_i <= a_i $
int main()
{
int n;
cin >> n;
unordered_map<int, int> primes;
while (n -- )
{
int x;
cin >> x;
for (int i = 2; i <= x / i; i ++ )
while (x % i == 0)
{
x /= i;
primes[i] ++ ;
}
if (x > 1) primes[x] ++ ;
}
LL res = 1;
for (auto p : primes) res = res * (p.second + 1) % mod;
cout << res << endl;
return 0;
}
约数之和
$ ( {p_1}^0 + {p_1}^1 +…+ {p_1}^{a_1} ) .... ( {p_k}^0 + {p_k}^1 +…+ {p_k}^{a_k} ) $
const int N = 110, mod = 1e9 + 7;
int main()
{
int n;
cin >> n;
unordered_map<int, int> primes;
while (n -- )
{
int x;
cin >> x;
for (int i = 2; i <= x / i; i ++ )
while (x % i == 0)
{
x /= i;
primes[i] ++ ;
}
if (x > 1) primes[x] ++ ;
}
LL res = 1;
for (auto p : primes)
{
LL a = p.first, b = p.second;
LL t = 1;
while (b -- ) t = (t * a + 1) % mod;
res = res * t % mod;
}
cout << res << endl;
return 0;
}
最大公约数
欧几里得算法
辗转相除法
gcd(a,b) = gcd( b , a%b )
int gcd( int a , int b ){
return b ? gcd( b , a%b ) : a;
}
// 或者直接调用(滑稽
__gcd( a , b );
欧拉函数
欧拉函数：1~n中与n互质的数的个数。
若在算数基本定理中，$N = p_1^{a_1}p_2^{a_2}p_m^{a_m}$，则
$ϕ(N)$ = $N \times \frac{p_1-1}{p_1} \times \frac{p_2-1}{p_2} \times\frac{p_m-1}{p_m}$
- 从1~N中去掉$p_1 , p_2 , p_3 .... p_k$的所有倍数。—> $ N - \frac{N}{p_1} - … - \frac{N}{p_K} $
- 因为第一步会去掉多余的数，所以我们需要加上所有${p_i}*{p_j} $ 的倍数。
—> $ N - \frac{N}{p_1} - … - \frac{N}{p_K} + \frac{N}{p_1*p_2} + … $ - 减去所有pi * pj * pk的倍数
求欧拉函数板子
int phi(int x)
{
int res = x;
// 分解质因数
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
筛法求欧拉函数
适用于求1~N中每一个数的欧拉函数
int primes[N], cnt;
int euler[N];
bool st[N];
void get_eulers(int n){
euler[1] = 1;
// 线性筛法
for (int i = 2; i <= n; i ++ ){
if (!st[i])
{
primes[cnt ++ ] = i;
euler[i] = i - 1;
}
for (int j = 0; primes[j] <= n / i; j ++ )
{
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0)
{
euler[t] = euler[i] * primes[j];
break;
}
euler[t] = euler[i] * (primes[j] - 1);
}
}
}
int main(){
int n;cin >> n;
get_eulers(n);
LL res = 0;
for (int i = 1; i <= n; i ++ ) res += euler[i];
cout << res << endl;
return 0;
}
