·基础数论
· \(gcd\)--(欧几里得算法)
\(gcd\)是最大公约数的缩写。
现在给定\(2\)个数，让你求$gcd( \ i , \ j \ ) $
-
$ O( n ) $
从 $ min( i , j ) $ 枚举到 $ 1 $ -
使用 \(gcd\) 函数.
伟大的欧几里得算法告诉我们： $ gcd(i,j)=gcd( i , j \ mod i ) $
· \(code\)
int gcd( int a , int b )
{
if( b == 0 ) return a ;
return gcd( b , a % b ) ;
}
· \(exgcd\)--（扩展欧几里得算法/裴蜀定理）
· $ First $ 裴蜀等式
一定存在一组\(x,y\)使得：
\[a \times x + b \times y = gcd( a , b ) \]·\(Second\)--扩展欧几里得算法
已知\(a,b\)求\(x,y\)满足上式。
证明：
\(\because\) $ gcd( a , b ) = gcd( b , a \ mod \ b ) $
设 \(x_0,y_0,x_1,y_1\)
一定存在
\[a \times x_0 + b \times y_0 = b \times x_1 + ( a \ mod \ b ) \times y_1 \]化简：
\[a \times x_0 + b \times y_0 = b \times x_1 + a \times y_1 - [ a \div b ] \times b \times y_1 \]移项得:
\[a \times x_0 + b \times y_0 = a \times y_1 + b \times ( x_1 - [a \div b ] \times b \times y_1 ) \]易知存在一组\(x_0,y_0,x_1,y_1\) (注意：是存在一组，不是一定相等。)
\[x_0 = y_1 \]\[y_0 = ( x_1 - [a \div b ] \times b \times y_1 ) \]·\(Third \ -- \ code\)
int exgcd( int a , int b , int &x , int &y )
{
if ( ! b )
{
x = 1;
y = 0;
return a;
}
int d = exgcd( b , a % b , x , y ) ;
int t = x ;
x = y ;
y = t - ( a / b ) * y ;
return d ;
}
·乘法逆元（数学上叫数论倒数）
·\(First\)--定义
如果 $ gcd( a , p ) = 1 $ ,则存在：
\[a \times x \equiv 1 (mod \ p) \]则称\(x\)是\(a\)模\(p\)的乘法逆元。\(x\) 写作 \(a^{-1}(mod \ p )\) 无歧义情况写作 \(a^{-1}\)
·\(Second\)
· 在同余式中，$ \beta \times a^{-1} \ 等价于 \ \beta \div a $
这个性质是逆元的最本质的用途。很容易证。
·求逆元
可以用\(快速幂\)， \(扩展欧几里得算法(gcd(a,b)=1)\)（单点），\(线性推逆元\)(所有)
这里说一下线性推。
已知 \(1^{-1} , ... , {(i-1)}^{-1} ( mod \ p )\)
求 $i^{-1} { mod \ p } $
设一个 $ k = [ p \div i ] $ , $j=p \ mod \ i $
那么易知：
\[k \times i + j \equiv 0 ( mod \ p ) \]两边同乘 $i^{-1} \times \ j^{-1} $
得：
\[k \times j ^{-1} \times i^{-1} \equiv 0( mod \ p ) \]两边同减 \(k \times j ^{-1}\) ，为防止出现负数，加上 $k \times p $
得：
\[i^{-1} \equiv k \times (p-j^{-1})(mod \ p ) \]\(\because\) $0 \le j < i $ ,
\(\therefore\) 可求 \(i^{-1}\)
·\(code\)
#define k p / i
const int p = 1e9 + 7 ;
int neoyong[ N ] ;
inline void _neoyong( )
{
neoyong[ 1 ] = 1 ;
for( int i = 2 ; i <= n ; ++ i )
{
neoyong[ i ] = ( k * ( p - neoyong[ p % i ] ) ) % p ;
}
}
·欧拉函数 \(\varphi(n)\)
·\(First\) -- 定义
在 \(1 .. n\) 中与 \(n\) 互质的数
例 $\varphi( \ 4 \ ) \ = \ 2 ( \ 1 \ , \ 3 \ ) $ ; $ \varphi( \ 10 \ ) \ = \ 4 $
· \(Second\) 求欧拉函数
·欧拉函数の拆解
现在给你\(n\)，让你求它的欧拉函数，一路推过去的时间复杂度是 $O( n \log n ) $ $ \ \ $ \(T\)
考虑拆解欧拉函数。
可利用容斥原理对其进行求解
设 $n = \prod_{i=1}^k p_i^{a_i} $
易知共有 \([n \div p_i ]\)个数整除 \(p_i\)
共有 $ [n \div ( p_i \times p_j ) ] $ 整除 $p_{ij} $
......共有 $[ n \div (\prod_{i=1}^k p_i) ] $ 数整除 \((\prod_{i=1}^k p_i)\)
整合一下
\[\varphi(n)=n \times \prod_{i=1}^k ( ( p_i - 1 ) \div p_i ) \]·单点
· \(code\)
int euler( int m )
{
int Euler = m ;
for( int i = 2 ; i <= sqrt( n ) ; ++ i )
{
if( m % i == 0 )
{
Euler = Euler / i * ( i - 1 ) ;
while( m % i == 0 )
{
m /= i ;
}
}
}
if( m > 1 )
{
Euler = Euler / m * ( m - 1 ) ;
}
return Euler ;
}
·线性
但万一它有多组数据呢？
线性推，你值得拥有。
考虑这个单点进行分类讨论。
- $ n \in \mathbb{P} $
显然 \(\varphi(n)=n-1\)
- $ ( n \div i ) \ mod \ i = 0 $
$\varphi(n) = \varphi(n \div i ) \times i $
因为 \(质因数\)的个数不变，前面的\(n\)扩大\(i\)倍。
\(\varphi(n)=n \times \prod_{i=1}^k ( ( p_i - 1 ) \div p_i )\)
\(\varphi(n\div i)=n \div i \times \prod_{i=1}^k ( ( p_i - 1 ) \div p_i )\)
\(k\) 不变，变的只是 \(n\div i -> n\)
- $ ( n \div i ) \ mod \ i \ne 0 $
除以 \(i\) 乘 \(i\) 除以 \(i-1\)和上面一个证明方法相似。
· \(code\)
void Euler( )
{
euler[ 1 ] = 1 ;
for( int i = 2 ; i <= n ; ++ i )
{
if( ! if_change[ i ] )
{
primes[ ++ now ] = i ;
euler[ i ] = i - 1 ;
}
for( int j = 1 ; primes[ j ] <= n / i ; ++ j )
{
if_change[ i * primes[ j ] ] = true ;
if( i % primes[ j ] == 0 )
{
euler[ i * primes[ j ] ] = euler[ i ] * primes[ j ] ;
break ;
}
euler[ i * primes[ j ] ] = euler[ i ] * ( primes[ j ] - 1 ) ;
}
euler[ i ] += euler[ i - 1 ] ;
}
}
·\(Thrid\) -- 一些定理
证明点这里
·费马小定理
（虽然和欧拉函数没啥关系，dam很有用）
当 \(gcd(a,p)=1\)
\[a^p \equiv a ( mod \ p ) \]·欧拉定理
当 \(gcd(a,p)=1\)
\[a^{\varphi(p)} \equiv 1 \pmod{p} \]·扩展欧拉定理
\[a^b \equiv \begin{cases}a^{b \bmod \varphi(p)} &\gcd(a,p)=1 \\ a^{b} &\gcd(a,p) \ne 1,b<\varphi(p) \\ a^{b \bmod \varphi(p)+\varphi(p)} &\gcd(a,p) \ne 1,b \ge \varphi(p)\end{cases} \pmod{p} \]·其它1
- \(First\)
-
\(Second\)
<1> \(若n是奇数：\) $ \varphi(2n) = \varphi(2) \times \varphi(n) $
<2> \(若a,b互质\) $ \varphi(a \times b) = \varphi(a) \times \varphi(b) $
\(ALL:\) 由上述两得知：欧拉函数是积性函数。