最大公约数 & 最小公倍数
Euclid's Algorithm：若\(b\neq0\)，那么\(gcd(a,b)=gcd(b,a\%b)\)
若\(a<b\)，定理会先交换a和b.
0和任意正整数a的gcd是a 1
2
3
4
5
6
7
8
9
10
11int gcd(int a, int b) {
return !b ? a : gcd(b, a % b);
}
int gcd(vector<int> nums) {
int res = nums[0];
for (int num : nums) {
res = gcd(num, res);
}
return res;
}
时间复杂度\(O(lgb)\)，因为每次递归问题规模都会缩减一半以上。
最小公倍数\(lcm=\frac{a*b}{gcd}\)
- 扩展欧几里得算法
可以计算出满足下式的三元组\((d,x,y)\)： \[d
= GCD(a, b) = ax + by\] 1
2
3
4
5
6
7
8
9
10
11int extendEuclid(int a, int b, int* x, int* y) {
if (0 == b) {
*x = 1, *y = 0;
return a;
}
int gcd = extendEuclid(b, a % b, x, y);
int temp = *x;
*x = *y;
*y = temp - (*y) * (a / b);
return gcd;
}
\(b=0\)是递归基，易得一组解\(x=1,y=0\);
\(b \neq0\)时：
首先递归求解：
\[d'=gcd(b,a\%b)=bx'+(a\%b)y' \ \
\ \ \ \ \ \ \ \ \ \ \ \ (1)\] 我们知道： \[d=gcd(a,b)=d'=gcd(b,a\%b)\ \ \ \ \ \ \ \ \ \
\ \ \ (2)\] \[a\%b=a-b*\biggl\lfloor
a/b \biggr\rfloor\ \ \ \ \ \ \ \ \ \ \ (3)\] 将(2)(3)式带入(1)：
\[d=bx'+(a-b\biggl\lfloor a/b
\biggr\rfloor)y'=ay'+b(x'-\biggl\lfloor a/b \biggr\rfloor
y')\] 所以，令\(x=y'\),
\(y=x'-\biggl\lfloor a/b \biggr\rfloor
y'\)，就可以满足\(d=ax+by\)
素数
- 判断素数
1
2
3
4
5
6
7
8
9
10bool isPrime(int n) {
if (n < 2) // 1不是素数，也不是合数
return false;
int square_root = sqrt(n);
for (int i = 2; i <= square_root; ++i) {
if (n % i == 0)
return false;
}
return true;
} - 打素数表
第一种方法是枚举判断, \(O(n^{1.5})\).
第二种是Eratosthenes筛法，复杂度\(O(nlog\
logn)\). 
1 | bool isprime[100005]; |
进一步的优化是欧拉筛，复杂度\(O(n)\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16bool isprime[maxn];
vector<int> primes;
void seive(int n) {
std::fill(isprime, isprime + n + 1, true);
for (int i = 2; i <= n; ++i) {
if (isprime[i])
primes.push_back(i);
for (int p : primes) {
if (p * i > n)
break;
isprime[p * i] = false;
if (i % p == 0)
break;
}
}
}
分解质因子
每个数都可以分解为质数的乘机, 注意1要特判.
枚举小于等于sqrt(n)内的所有质因子, 判断哪个是n的因子.
1 | vector<pair<int, int>> primeBreak(int n) { |
分数
PAT甲1088是比较经典的分数处理问题，求2个分数的和、差、积、商，输出最简形式。
表示、化简、运算、输出，代码阐释得很清楚。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) {
return !b ? a : gcd(b,a % b);
}
struct Fraction {
ll nume,deno;
};
Fraction reduction(Fraction a) {
if(a.deno < 0) {
a.deno = -a.deno;
a.nume = -a.nume;
}
if(a.nume == 0) {
a.deno = 1;
}
else {
int d = gcd(abs(a.nume),abs(a.deno));
a.nume /= d;
a.deno /= d;
}
return a;
}
Fraction add(Fraction a,Fraction b) {
Fraction res;
res.deno = a.deno * b.deno;
res.nume = a.deno * b.nume + a.nume * b.deno;
return reduction(res);
}
Fraction sub(Fraction a,Fraction b) {
Fraction res;
res.deno = a.deno * b.deno;
res.nume = a.nume * b.deno - a.deno * b.nume;
return reduction(res);
}
Fraction times(Fraction a,Fraction b) {
Fraction res;
res.deno = a.deno * b.deno;
res.nume = a.nume * b.nume;
return reduction(res);
}
Fraction divide(Fraction a,Fraction b) {
Fraction res;
res.deno = a.deno * b.nume;
res.nume = a.nume * b.deno;
return reduction(res);
}
void showFrac(Fraction a) {
a = reduction(a);
if(a.nume < 0) {
printf("(");
}
if(a.deno == 1) {
printf("%lld",a.nume);
}
else if(abs(a.nume) > abs(a.deno)) {
printf("%lld %lld/%lld",a.nume / a.deno,abs(a.nume) % a.deno,a.deno);
}
else {
printf("%lld/%lld",a.nume,a.deno);
}
if(a.nume < 0) {
printf(")");
}
}
int main() {
Fraction a,b;
scanf("%lld/%lld%lld/%lld",&a.nume,&a.deno,&b.nume,&b.deno);
showFrac(a);
printf(" + ");
showFrac(b);
printf(" = ");
showFrac(add(a,b));
printf("\n");
showFrac(a);
printf(" - ");
showFrac(b);
printf(" = ");
showFrac(sub(a,b));
printf("\n");
showFrac(a);
printf(" * ");
showFrac(b);
printf(" = ");
showFrac(times(a,b));
printf("\n");
showFrac(a);
printf(" / ");
showFrac(b);
printf(" = ");
if(b.nume == 0) {
printf("Inf\n");
}
else {
showFrac(divide(a,b));
printf("\n");
}
return 0;
}
