[AcWing],数学知识(二),证明推导欧拉函数,快速幂,扩展欧几里得算法-爱代码爱编程
欧拉函数
欧拉公式
对于每一个数 N N N,都可以分解为 N = p 1 α 1 × p 2 α 2 × ⋯ × p k α k N=p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k} N=p1α1×p2α2×⋯×pkαk
其中, p 1 p 2 ⋯ p k p_1 p_2 \cdots p_k p1p2⋯pk为质数, α 1 α 2 ⋯ α k \alpha_1 \alpha_2 \cdots \alpha_k α1α2⋯αk为对应的质数的出现次数
那么,最后的结果为 r e s = N × p 1 − 1 p 1 × p 2 − 1 p 2 × ⋯ × p k − 1 p k res = N \times \frac{p_1 - 1}{p_1} \times \frac{p_2 - 1}{p_2} \times \cdots \times \frac{p_k - 1}{p_k} res=N×p1p1−1×p2p2−1×⋯×pkpk−1
需要注意的一点
当我们在计算 N × p 1 − 1 p 1 N \times \frac{p_1 - 1}{p_1} N×p1p1−1的时候,如果我们用 N × ( p 1 − 1 ) N\times (p_1 - 1) N×(p1−1),那么很容易发生溢出,所以我们采取先计算除法,在计算乘法
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
while (n --) {
int x;
cin >> 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);
cout << res << endl;
}
return 0;
}
筛法求欧拉函数
思路:
- 实现线性筛选法来筛选每一个质数
- 对于一个质数 P n P_n Pn来说,他的一个欧拉函数为 P n − 1 P_n - 1 Pn−1
- 对于一个和数 P n P_n Pn来说,在我们线性筛选质数的过程中,他需要分两种情况:
①. i%primes[j] == 0
,说明
p
r
i
m
e
s
[
j
]
primes[j]
primes[j]是
i
i
i的最小质因子,也是
i
×
p
r
i
m
e
s
[
j
]
i \times primes[j]
i×primes[j]的最小质因子。所以说,只需要将一开始的基数修改为
p
r
i
m
e
s
[
j
]
primes[j]
primes[j]即可
r
e
s
(
i
)
=
i
×
p
1
−
1
p
1
×
p
2
−
1
p
2
×
⋯
×
p
k
−
1
p
k
(
i
=
p
k
)
res(i) = i \times \frac{p_1 - 1}{p_1} \times \frac{p_2 - 1}{p_2} \times \cdots \times \frac{p_k - 1}{p_k}(i=p_k)
res(i)=i×p1p1−1×p2p2−1×⋯×pkpk−1(i=pk) i
是一个质数
⇒ r e s ( p r i m e s [ j ] × i ) = p r i m e s [ j ] × i × r e s ( i ) i \Rightarrow res(primes[j] \times i) = primes[j] \times i \times \frac{res(i)}{i} ⇒res(primes[j]×i)=primes[j]×i×ires(i)
⇒ r e s ( p r i m e s [ j ] × i ) = p r i m e s [ j ] × r e s ( i ) \Rightarrow res(primes[j] \times i) = primes[j] \times res(i) ⇒res(primes[j]×i)=primes[j]×res(i)
② .i % primes[j] != 0
,说明
p
r
i
m
e
s
[
j
]
primes[j]
primes[j]不是
i
i
i的因子,只是
i
×
p
r
i
m
e
s
[
j
]
i \times primes[j]
i×primes[j]的最小质因子。因此,修改基数
1
1
1为
p
r
i
m
e
s
[
j
]
primes[j]
primes[j]后,还需要补上
p
r
i
m
e
s
[
j
]
primes[j]
primes[j]这个质数的欧拉函数项
r e s ( i ) = i × p 1 − 1 p 1 × p 2 − 1 p 2 × ⋯ × p k − 1 p k res(i) = i \times \frac{p_1 - 1}{p_1} \times \frac{p_2 - 1}{p_2} \times \cdots \times \frac{p_k - 1}{p_k} res(i)=i×p1p1−1×p2p2−1×⋯×pkpk−1
⇒ r e s ( p r i m e s [ j ] × i ) = p r i m e s [ j ] × i × r e s ( i ) i × p r i m e s [ j ] − 1 p r i m e s [ j ] \Rightarrow res(primes[j] \times i) = primes[j] \times i \times \frac{res(i)}{i} \times \frac{primes[j] - 1}{primes[j]} ⇒res(primes[j]×i)=primes[j]×i×ires(i)×primes[j]primes[j]−1
⇒ r e s ( p r i m e s [ j ] × i ) = r e s ( i ) × ( p r i m e s [ j ] − 1 ) \Rightarrow res(primes[j] \times i) = res(i)\times (primes[j] - 1) ⇒res(primes[j]×i)=res(i)×(primes[j]−1)
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int primes[N],phi[N],cnt;
int vis[N];
int n;
void get_phi() {
phi[1] = 1;
for(int i = 2; i <= n; i++) {
if(!vis[i]) {
primes[cnt++] = i;
phi[i] = i - 1;
}
for(int j = 0; primes[j] <= n / i; j ++) {
vis[primes[j] * i] = 1;
if(i % primes[j] == 0) {
phi[primes[j] * i] = phi[i] * primes[j];
break;
}
phi[primes[j] * i] = phi[i] * (primes[j] - 1);
}
}
}
int main() {
cin >> n;
get_phi();
LL res;
for(int i = 1; i <= n; i++) res += phi[i];
cout << res << endl;
return 0;
}
快速幂
快速幂
思路
- 当指数 k k k为 0 0 0的时候,返回 1 1 1
- 当指数 k k k为奇数的时候,返回 x × x k − 1 × x k − 1 x \times x^{k-1} \times x^{k-1} x×xk−1×xk−1
- 当指数 k k k为偶数的时候,返回 x k / 2 × x k / 2 x^{k/2} \times x^{k/2} xk/2×xk/2
- 递归
#include <iostream>
using namespace std;
typedef long long LL;
int n,a,b,c;
LL check(int k) {
if(k == 0) return 1;
if(k & 1) return check(k - 1) % c * a % c;
LL x = check(k / 2);
return (x * x) % c;
}
int main() {
cin >> n;
while(n --) {
cin >> a >> b >> c;
cout << check(b) << endl;
}
return 0;
}
- 递推
#include <iostream>
using namespace std;
typedef long long LL;
int n,a,b,c;
LL check() {
LL res = 1;
while(b) {
if(b & 1) res = res * a % c;
a = (LL) a * a % c;
b >>= 1;
}
return res;
}
快速幂求逆元
当 n n n为质数的情况
a / b ≡ a × x ( m o d n ) a/b \equiv a \times x \pmod{n} a/b≡a×x(modn)
同时
×
b
\times b
×b可以推导出
⇒
a
≡
a
×
b
×
x
(
m
o
d
n
)
\Rightarrow a \equiv a \times b \times x\pmod{n}
⇒a≡a×b×x(modn)
⇒
1
≡
b
×
x
(
m
o
d
n
)
\Rightarrow 1 \equiv b \times x \pmod{n}
⇒1≡b×x(modn)
⇒
b
×
x
≡
1
(
m
o
d
n
)
\Rightarrow b \times x \equiv 1\pmod{n}
⇒b×x≡1(modn)
费马小定理: 如果p是一个质数,而整数a不是p的倍数,则有 a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1\pmod{p} ap−1≡1(modp)
由费马小定理可知,当
n
n
n为质数时,
b
n
−
1
≡
1
(
m
o
d
n
)
b ^{n-1} \equiv 1 \pmod{n}
bn−1≡1(modn)
⇒
b
×
b
n
−
2
≡
1
(
m
o
d
n
)
\Rightarrow b \times b ^{n-2} \equiv 1\pmod{n}
⇒b×bn−2≡1(modn)
所以说,当n为质数时,b的乘法逆元为
x
=
b
n
−
2
(
m
o
d
n
)
x=b^{n-2}\pmod{n}
x=bn−2(modn)
#include <iostream>
using namespace std;
typedef long long LL;
int n;
void check(int a,int b,int p) {
LL res = 1;
while(b) {
if(b & 1) res = (res * a) % p;
b >>= 1;
a = ((LL)a * a) % p;
}
cout << res << endl;
}
int main() {
cin >> n;
while( n --) {
int a,p;
cin >> a >> p;
if(a % p == 0) puts("impossible");
else check(a,p-2,p);
}
return 0;
}
扩展欧几里得算法
当 n n n不为质数时的情况
扩展欧几里得算法,用于求
a
x
+
b
y
=
gcd
(
a
,
b
)
ax+by=\gcd(a,b)
ax+by=gcd(a,b)的解
⇒
e
x
g
c
d
(
a
,
b
,
x
,
y
)
\Rightarrow exgcd(a,b,x,y)
⇒exgcd(a,b,x,y)
那么,当 b = = 0 b==0 b==0的时候, a x + b y = a ⇒ a x + b × 0 = a ax+by=a \Rightarrow ax+b \times 0 =a ax+by=a⇒ax+b×0=a
⇒ a x = a \Rightarrow ax=a ⇒ax=a
⇒ x = 1 , y = 0 \Rightarrow x=1 ,y = 0 ⇒x=1,y=0
当 b ! = 0 b!=0 b!=0的时候, a x + b y = gcd ( a , b ) = gcd ( b , a % b ) ax+by=\gcd(a,b)= \gcd(b,a\%b) ax+by=gcd(a,b)=gcd(b,a%b)
⇒ b x ′ + ( a % b ) y ′ = gcd ( b , a % b ) \Rightarrow bx' + (a\%b)y'=\gcd(b,a\%b) ⇒bx′+(a%b)y′=gcd(b,a%b)
⇒ b x ′ + ( a − ⌊ a b ⌋ × b ) y ′ = gcd ( b , a % b ) \Rightarrow bx' + (a - \left \lfloor \frac{a}{b} \right \rfloor \times b)y'=\gcd(b,a\%b) ⇒bx′+(a−⌊ba⌋×b)y′=gcd(b,a%b)
⇒ a y ′ + b ( x ′ − ⌊ a b ⌋ × y ′ ) = gcd ( b , a % b ) = gcd ( a , b ) \Rightarrow ay' + b(x' - \left \lfloor \frac{a}{b} \right \rfloor \times y')=\gcd(b,a\%b)=\gcd(a,b) ⇒ay′+b(x′−⌊ba⌋×y′)=gcd(b,a%b)=gcd(a,b)
所以说,可以得到的结果是 x = y ′ , y = x ′ − ⌊ a b ⌋ × y ′ x=y',y = x' - \left \lfloor \frac{a}{b} \right \rfloor \times y' x=y′,y=x′−⌊ba⌋×y′
#include <iostream>
using namespace std;
int n;
void exgcd(int a,int b,int& x,int& y) {
if(!b) {
x = 1, y = 0;
return ;
}
int tx,ty;
exgcd(b,a % b,tx,ty);
x = ty, y = tx - a/b * ty;
}
int main() {
cin >> n;
while (n --) {
int a,b,x,y;
cin >> a >> b;
exgcd(a,b,x,y);
cout << x << " " << y << endl;
}
return 0;
}
线性同余方程
给定
n
n
n组数据
a
i
,
b
i
,
m
i
a_i,b_i,m_i
ai,bi,mi,对于每组数求出一个
x
i
x_i
xi,使其满足
a
i
×
x
i
≡
b
i
(
m
o
d
m
)
i
a_i \times x_i≡b_i \pmod m_i
ai×xi≡bi(modm)i
经过变化后可以得出:
a
i
×
x
i
−
m
i
×
y
i
=
b
i
a_i \times x_i -m_i \times y_i = b_i
ai×xi−mi×yi=bi
⇒
a
i
×
x
i
+
m
i
×
y
i
=
b
i
\Rightarrow a_i \times x_i +m_i \times y_i = b_i
⇒ai×xi+mi×yi=bi
所以说,就可以使用扩展欧几里得算法求出 x i x_i xi的值,然后判断该等式方程是否存在解
该方程式存在解的充分必要条件是: b b b是 a a a和 m m m的最大公约数 d d d的倍数
那么,我们最后使用扩展欧几里得算法所求出的结果
x
x
x是基于
a
a
a和
m
m
m最大公约数的一个结果,想要求出和
b
b
b相关的结果,需要将
x
x
x扩大
b
÷
d
b \div d
b÷d倍
x
=
x
×
b
÷
d
(
m
o
d
m
)
x = x \times b \div d \pmod m
x=x×b÷d(modm)
#include <iostream>
using namespace std;
int n;
typedef long long LL;
int exgcd(int a,int b,int& x,int& y) {
if(!b) {
x = 1, y = 0;
return a;
}
int x1,y1;
int ret = exgcd(b,a%b,x1,y1);
x = y1;
y = x1 - a / b * y1;
return ret;
}
int main() {
cin >> n;
while(n --) {
int a,b,m,x,y;
cin >> a >> b >> m;
int d = exgcd(a,m,x,y);
if(b % d) puts("impossible");
else {
x = (LL)x * b / d % m;
cout << x << endl;
}
}
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/duchenlong/article/details/112534599