介绍基础性算法
双指针问题
- 最长连续不重复子序列
时间负责度是 $O(n)$
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
|
#include<iostream>
using namespace std;
const int N =100000 +11;
int n;
int arr[N];
int tmp[N];
int main()
{
cin >>n;
for(int i =0; i< n ;i++)
scanf("%d",&arr[i]);
int res =0;
for(int i =0,j =0; i< n; i++)
{
tmp[arr[i]] ++;
while(j< i && tmp[arr[i]] >1)
{
tmp[arr[j++]] --;
}
//cout << i<< " "<< j<<endl;
res =max(res, i -j +1);
}
cout << res<<endl;
return 0;
}
|
- 数组元素的目标和
要使用双指针算法，就要找到其中的单调性。当i，j 分别指向 A数组的开头和B 数组的结尾。当 i 向右移动，那么与之对应的j 必然在原先的左边。所以这就符合单调性的要求，那么就可以使用双指针来做。
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
|
#include<iostream>
#include<vector>
using namespace std;
const int N = 100000+11;
int n, m, x;
int A[N];
int B[N];
int main()
{
cin >>n >>m >>x;
for(int i =0; i< n; i++)
scanf("%d", &A[i]);
for(int i =0; i< m; i++ )
scanf("%d", &B[i]);
// 使用双指针算法，必然需要找到其中的单调性，
for(int i =0, j =m -1; i< n ; i++)
{
while(j >=0 && A[i] +B[j] > x) j --;
if(A[i] +B[j] ==x) printf("%d %d", i, j);
}
return 0;
}
|
- 最长不含重复字符的子字符串
这道题目和上一道题目是很相似的。。第一种解法是是双指针解法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
int longestSubstringWithoutDuplication(string s) {
unordered_map<char, int> has;
// 双指针问题
int n =s.size() ;
int res =0;
for(int i =0, j =0; i< n; i++ )
{
has[s[i]] ++;
while( j< i && has[s[i]] >1)
{
has[s[j]] --; // 求解的长度，可以先减一个嘴说
j ++;
}
res =max(res, i -j +1);
}
return res;
}
};
|
第二种解法是dp 解法。
字符流中第一个只出现一次的字符
对于这种重复不重复的题目，经常使用的就是 dictionary 进行判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution{
public:
// 队列模拟读入和弹出的过程，
// 到底 什么是dictionary，就是一个快速访问的数据结构，从key 到value的那种
//Insert one char from stringstream
unordered_map<char, int> dic;
queue<char> q;
void insert(char ch){
if( ++dic[ch] >1)
{
while(q.size() && dic[q.front()] >1) q.pop();
}
else
q.push(ch);
}
//return the first appearence once char in current stringstream
char firstAppearingOnce(){
if(q.size() >=1) return q.front();
else return '#';
}
};
|
- 调整数组顺序使奇数位于偶数前面
两个指针相遇，走过的总路程是$n$, 所以时间复杂度是$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
void reOrderArray(vector<int> &array) {
int l =0, r =array.size() -1;
while(l< r)
{
while(l < r && array[l] %2 ==1) l ++;
//int t=array[l];
while(l< r && array[r] %2 ==0) r --;
if(l< r) swap(array[l], array[r]);
}
}
};
|
- 和为S的连续正数序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
// 使用i j 两个指针操作
vector<vector<int> > findContinuousSequence(int sum) {
int i=1, j =2;
vector<vector<int>> res;
while(i < j && j< sum)
{
int total = (j -i+1) *(i +j);
if(total == 2*sum)
{
vector<int> level;
for(int k =i; k<=j ; k++) level.push_back(k);
res.push_back(level);
level.clear();
i ++, j ++;
}
else if(total > 2*sum) i ++;
else j ++;
}
return res;
}
};
|
翻转单词顺序
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
|
class Solution {
public:
// 需要翻转两次，一次以字母为单位全翻转，一次以单词为单位翻转
// 可以处理前后有空格，中间有多余的空格的情况
string reverseWords(string s) {
int k =0;// k存储的是有效的长度
for(int i =0; i< s.size() ; i++)
{
// 找到字母开始
int j =i;
while(j < s.size() && s[j] ==' ') j ++; // j指向的是非空格
if (j ==s.size()) break;
// 找到字母的结束
i =j;
while(j < s.size() && s[j] !=' ') j++;// j指向的是空格
//细节，
if(k) s[k++] =' ';
reverse(s.begin() +i, s.begin() +j);// 左闭右开
while(j -i) s[k++] =s[i++];
}
s.erase(s.begin() +k, s.end());
reverse(s.begin(), s.end());
return s;
}
};
|
- 纪念品分组
贪心算法 + 双指针（题目还是有一定的规律，比如，操作 j– 那么必须 j>=0 ），对于贪心，常见的套路就是 先排序，然后选择“价值” 最大的。对于双指针常见的写法 for 循环然后是while 循环。本题的时间复杂度是 $O(nlogn)$. 上限是sort() 函数的排序算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 30000 +11;
int a[N];
bool st[N];
int main()
{
int w,n;
cin >>w>> n;
for(int i =0; i< n; i++) cin >> a[i];
sort(a, a+n);
int res =0;
// 尽可能贪心的选择，选择两个，然后选择价值最大的
for(int i =0, j =n -1; i< n;i++)
{
if(st[i]) continue;
while( j >= 0&&( st[j] || a[i] +a[j] >w )) j --;
st[i] =st[j] =true;
res +=1;
}
cout<< res <<endl;
return 0;
}
|
所以模板可以处理两类问题。
1
2
3
4
5
6
7
8
9
|
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
// 具体问题的逻辑
}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
|
75. Sort Colors
时间复杂度是 $O(n)$ ，空间复杂度是$O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
// l 和r 分别表示 01 边界问题， 12 边界问题
void sortColors(vector<int>& nums) {
int l =0, r =nums.size() -1;
int index =0;
// 注意这个边界条件
while( index<=r )
{
if(nums[index] ==1) index ++;
else if(nums[index] ==0) swap(nums[index++], nums[l++]);
else swap(nums[index], nums[r--]);
}
}
};
|
时间复杂度是 $NlogN$
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
|
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
const int N =1e5+11;
typedef pair<int, int> PAIR;
int n;
vector<PAIR> arr;
void merge(vector<PAIR> & segs)
{
vector<PAIR> res;
sort(segs.begin(), segs.end());
int l =-2e9, r =-2e9;
for(auto seg : segs)
{
// 好好理解为什么之类是 first
if(seg.first > r)
{
if( l != -2e9) res.push_back({l, r});
l =seg.first, r =seg.second;
}
else r =max(r, seg.second);
}
if(l != -2e9) res.push_back({l, r});
segs =res;
}
int main()
{
cin >> n;
for(int i =0; i< n; i ++)
{
int a, b;
scanf("%d %d", &a, &b);
arr.push_back({a, b});
}
merge(arr);
cout << arr.size() << endl;
return 0;
}
|
Insert Interval
时间复杂度是 $O(n)$，空间复杂度是$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
// 这个题目相对于 合并区间是简单的，因为一开始有有序的，然后加入一个无序的，总的是 O(n)
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> res;
int i=0, n =intervals.size();
// 如果intervals 中的一部分是小于 newInterval的左边
while( i < n && intervals[i][1] < newInterval[0])
{
res.push_back(intervals[i++]);
}
// 如果intervals 中的某一个和 newInterval 有交集
while(i <n && intervals[i][0] <= newInterval[1])
{
newInterval[0] =min(intervals[i][0], newInterval[0]);
newInterval[1] =max(intervals[i][1], newInterval[1]);
i++;// 这里非常容易拉掉 i ++
}
res.push_back(newInterval);
while(i< n ) res.push_back(intervals[i++]);
return res;
}
};
|
高精度计算
在32位或64位机器中，int占4个字节，即32位。C/C++规定该值为-2^31=-2147483648（大概是 21 亿的样子）。longlong 是64位。在字符串处理的时候，加法和乘法需要加上t(如果最后t >0)， 对于除法和减法，需要去掉最后多余的0.
高精度加法
基本上是正序处理加法，然后是逆序输出和输入。
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
|
#include<iostream>
#include<vector>
#include<string>
using namespace std;
vector<int> add(vector<int> & a, vector<int> & b)
{
vector<int> res;
int t =0;
// 这个 i相当于是每次处理的数字
// 这里的 || 是一个细节，如果是，是需要这样写的
for(int i =0 ; i< a.size() || i< b.size() ; i++ )
{
if(i < a.size() ) t += a[i];
if( i< b.size() ) t += b[i];
res.push_back(t %10);
t =t/10;
}
if(t >0) res.push_back(t);
return res;
}
int main()
{
string a, b;
cin>> a>> b;
vector<int> A, B;
// 从低位往高位计算的
for(int i =a.size() -1; i>=0 ; i--) A.push_back(a[i] -'0');
for(int i =b.size() -1; i>=0. ; i--) B.push_back(b[i] -'0');
// 输出也很对称，也是逆序输出，因为先处理的低位，然后低位是push_back() 到后面了，应该是最后输出
vector<int> res =add(A, B);
for(int i =res.size()-1 ; i>=0 ; i-- ) cout<< res[i];
cout <<endl;
return 0;
}
|
高精度减法
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
|
#include<vector>
#include<string>
#include<iostream>
using namespace std;
bool cmp(vector<int>& a, vector<int>& b)
{
if(a.size() != b.size() ) return a.size() > b.size() ;
for(int i =0; i< a.size() ; i++)
{
if(a[i] != b[i] ) return a[i] >b[i];
}
return true;
}
// a>=b
vector<int> sub(vector<int>& a, vector<int>& b)
{
vector<int> res;
int t =0;
for(int i =0; i< a.size() ; i++)
{
t = a[i] -t;
if(i < b.size()) t -= b[i];
res.push_back( (t+10) %10);
// 加法中补位操作
if(t <0) t =1;
else t =0;
}
// 去0 的操作
while(res.size() >0 && res.back() == 0) res.pop_back();
return res;
}
int main()
{
string a, b;
cin >> a>> b;
vector<int> A, B;
for(int i =a.size() -1; i>=0 ; i--) A.push_back(a[i]);
for(int i =b.size() -1; i>=0; i--) B.push_back(b[i]);
// a >= b
if(cmp(A, B))
{
vector<int> c =sub(A, B);
for(int i =c.size() -1; i>=0; i--) cout << c[i];
}
else
{
vector<int> c =sub(B, A);
cout << '`';
for(int i =c.size() -1; i>=0; i--) cout << c[i];
}
return 0;
}
|
高精度乘法
两个数字是不一样的，一个是需要使用string 表示，一个是使用int 表示就行。
1
2
|
1≤A的长度≤100000
1≤B≤10000
|
实现代码
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
|
#include<iostream>
#include<vector>
#include<string>
using namespace std;
vector<int> multiply(vector<int> a, int b)
{
vector<int> res;
// 这个判断条件也是比较精巧的
int t=0;
for(int i =0; i< a.size() || !b ; i++)
{
if(i < a.size()) t +=a[i] *b;
res.push_back(t %10);
t /= 10;
}
return res;
}
// 对于大数转成字符串，逆序，然后处理，逆序输出，这个就是非常common 的操作了
int main()
{
string a;
int b ;
cin >> a>> b;
vector<int> A;
for(int i =a.size() -1; i>=0; i--) A.push_back(a[i] -'0');
vector<int> res =multiply(A, b);
for(int i =res.size() -1; i>=0 ; i--) cout << res[i];
return 0;
}
|
乘法还是比较nice 的。
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
|
#include<string>
#include<vector>
#include<iostream>
using namespace std;
vector<int> a, c;
int b;
void multiply()
{
int t =0;
for(int i =0; i< a.size(); i++)
{
t += a[i] *b;
c.push_back(t %10);
t /=10;
}
if(t >0) c.push_back(t);
}
int main()
{
string A;
cin>> A ;
cin >> b;
for(int i =A.size() -1; i>=0; i--) a.push_back(A[i] -'0');
multiply();
for(int i =c.size() -1; i>=0 ; i--) cout <<c[i];
cout << endl;
return 0;
}
|
高精度除法
（个人感觉这个叫做大数除法更加合适）
给定两个正整数A，B，请你计算 A / B的商和余数。
高精度除法
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
|
#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> res;
void divide(vector<int> & a, int b , int & r)
{
for(int i =0 ; i< a.size() ; i++)
{
r =10*r +a[i];
res.push_back(r /b);// 这个是结果求商的
r %= b;
}
reverse(res.begin(), res.end());
while(res.size() >0 && res.back() ==0) res.pop_back();
}
int main()
{
string A;
vector<int> a;
int b;
cin >> A;
cin >> b;
for(int i =0; i< A.size() ; i++) a.push_back(A[i] -'0');
int r =0;
divide(a, b, r);
// 有时候segment 错误真的是很烦，因为很有可能是下标的问题，不能访问导致的错误。
for(int i =res.size() -1; i>=0 ; i--) cout << res[i];
cout << endl;
cout<< r<< endl;
return 0;
}
|
思想很简单，使用一个 $O(n)$ 的预处理，然后再 $O(1)$ 的时间内就可以基三每个查询。所以总的时间复杂度是 $O(n)$ 空间是 $O(N)$. 关键在于背会模板，注意边界条件。
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
|
#include<iostream>
#include<vector>
using namespace std;
const int N =1e5;
int n,m;
int arr[N];
int pre[N];
// 记录原来的序列，空间 O(n) 时间是 O(n)
int main()
{
int l, r;
cin>> n>>m;
for(int i =1; i<=n; i++)
{
int tmp;
cin >>tmp;
arr[i] =tmp;
}
for(int i =1; i<=n; i++)
{
pre[i] =pre[i-1] +arr[i];
}
while(m --)
{
cin >> l >>r;
cout << pre[r] -pre[l-1] <<endl;
}
return 0;
}
|
还有一个写法是，不用保存原来的数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include<iostream>
#include<vector>
using namespace std;
const int N =1e5+11;
int n, m;
int pre[N];
int main()
{
cin >>n>>m;
int l, r;
for(int i=1; i<=n ; i++)
{
int tmp;
cin >> tmp;
// pre[i-1] 表示之前的累加和
pre[i] = pre[i-1] +tmp;
}
while(m --)
{
cin >> l >>r;
cout << pre[r] -pre[l-1]<< endl;
}
return 0;
}
|
二维前缀和的定义还是很重要的，看图
- $S[i,j]S[i,j] $即为图中红框中所有数的的和为：
$$S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j]S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j]$$
- $(x1,y1),(x2,y2)(x1,y1),(x2,y2) $这一子矩阵中的所有数之和为：
$$S[x2,y2]−S[x1−1,y2]−S[x2,y1−1]+S[x1−1,y1−1]$$
这道题目的关键是搞清下标，最后再求解某一个区间的面积的时候， $s[x1-1][y2] $和 $s[x2][y1-1] $注意这点。
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
|
#include<iostream>
#include<cstdio>
using namespace std;
const int N =1011;
int s[N][N];
//int a[N][N];
int n,m, q;
int main()
{
cin >>n>>m >>q;
for(int i=1; i<=n; i++)
{
for(int j =1; j<=m ; j++)
{
//scanf("%d", &a[i][j]);
int tmp;
scanf("%d", &tmp);
s[i][j] = s[i-1][j] +s[i][j -1] -s[i-1][j-1] + tmp;
}
}
while(q--)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
// 关键是下标呀
printf("%d\n", s[x2][y2] - s[x1-1][y2] -s[x2][y1-1] + s[x1-1][y1-1]);
}
return 0;
}
|
前缀和差分是2个互逆的运算。
这种策略是，令$b_i = a_i - a_{i-1} $，即相邻两数的差。
易得对这个序列做一遍前缀和就得到了原来的 $a$序列。
它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。（总之修改操作一定要在查询操作之前）
具体怎么搞？譬如使 $[l, r]$ 每个数加上一个 $k$ ，就是 $b_l \leftarrow b_l+k $, $b_{r+1} \leftarrow b_{r+1} - k$ 。
最后做一遍前缀和就好了。
注意特殊处：这道题是先进行整体区间修改，最后才统一查询。 所以，我们只要维护一个差分数组就行了。总的来说差分数组适用于离线的区间修改问题，如果是在线的话应该用线段树或其他数据结构。
为什么要存差值呢？————因为数列中的数满 $A[i]=sum{D[1]…D[i]} $,便于用递推求得最后的值。
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
|
#include<iostream>
using namespace std;
const int N =1e5+11;
int n, m;
int arr[N];
int s[N];
int main()
{
cin >> n>>m;
for(int i =1; i<= n; i++)
scanf("%d", &arr[i]);
for(int i =1; i<=n; i++)
s[i] =arr[i] -arr[i-1];
while(m --)
{
int l, r,c;
cin >> l>> r>>c;
s[l] +=c;
s[r+1] -=c;
}
// 求解一个前缀和
for(int i =1; i<=n ; i++)
{
s[i] += s[i-1];
cout << s[i]<<' ';
}
return 0;
}
|
- 差分矩阵
讲解
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
|
#include<iostream>
using namespace std;
const int N =1011;
// 构造差分矩阵
// 维护差分矩阵
// 求解前项和，然后输出
int a[N][N];
int b[N][N];
// 在 (x1, y1) 和 (x2, y2)这个范围内 +c
void insert(int x1, int y1, int x2, int y2, int c)
{
b[x1][y1] +=c;
b[x2+1][y1] -= c;
b[x1][y2+1] -=c;
b[x2+1][y2+1] += c;
}
int main()
{
int n, m, q;
cin >>n>>m>>q;
for(int i =1; i<= n; i++)
{
for(int j =1; j<= m; j++)
{
scanf("%d",&a[i][j]);
insert(i, j, i, j, a[i][j]);
}
}
while(q--)
{
int x1, y1, x2, y2, c;
cin>> x1>> y1 >>x2>> y2>>c;
insert(x1, y1, x2, y2, c);
}
for(int i =1; i<=n ; i++)
{
for(int j =1; j<=m ; j++)
{
b[i][j] +=b[i-1][j] +b[i][j-1] -b[i-1][j-1];
printf("%d ", b[i][j]);
}
puts("");
}
return 0;
}
|
区间专题
解题思路：绝大部分涉及到区间的题目第一步要做的都是按照左端点或者右端点进行排序，排好序后找到其中的递推关系。具体到这一题，我们可以先把问题转化成最多能找到多少个互不重叠的区间。
57. Insert Interval
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
|
class Solution {
public:
// 这个相对于前一个的思路可能是比较难的，该如何做呢？
// 需要设置一个特殊的标志位，表示是否已经把 newInterval 处理掉了
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newinter) {
bool flag =false;
vector<vector<int>> res;
int n =intervals.size();
for(int i =0; i< n; i++)
{
if(newinter[1] < intervals[i][0])
{
if(!flag){
res.push_back(newinter);
flag =true;
}
// 如果已经处理过 newinter ，这个时候就可以不断的加入区间到最后的结果中去
res.push_back(intervals[i]);
}
else if(intervals[i][1] < newinter[0])
{
res.push_back(intervals[i]);
}
else
{
newinter[0] =min(newinter[0], intervals[i][0]);
newinter[1] =max(newinter[1], intervals[i][1]);
}
}
//cout << flag<< endl;
if(!flag)
{
res.push_back(newinter);
}
return res;
}
};
|
数学知识
- 判断质数
一个数的因数都是成对出现的：例如12 的因数有3 和4，2和6.所以我们是可以枚举较小的那个，即根号n，假设较小的是d，较大的是n /d
prime，素数和质数是一个意思，合数是其相反的方面。
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
|
// 0和1 既非质数也非合数，2 是最小的质数，最大的质数不存在
// 对于质数的定义，如果a 只能被1 和本身整除，那么a 就是质数(a >2)
#include<bits/stdc++.h>
using namespace std;
bool is_prime(int x)
{
if(x < 2) return false;
for(int i =2; i<= x/i; i++)
{
if(x %i ==0) return false;
}
return true;
}
int main()
{
int n;
cin >>n;
for(int i =0; i<n; i++)
{
int tmp;
cin >>tmp;
if(is_prime(tmp)) cout << "Yes"<<endl;
else cout << "No" << endl;
}
return 0;
}
|
- AcWing 867. 分解质因数
有了上面的质数，那么再求解一个数字的质因数分解，应该不是很难的事情。
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
|
#include<bits/stdc++.h>
using namespace std;
// 质因数分解， 这个是能够保证过程中 i 是质数的
void divide(int n)
{
for(int i =2; i<=n ; i++)
{
// 住一个这个过程中n 是不断减少的，所以这个复杂度不是n^2
if( n%i ==0)
{
int s =0; // 对于 i 这个质因数，couts 是多少?
while(n %i ==0) n /=i, s++;
cout << i <<" "<< s<< endl;
}
}
if(n >1) cout << n << " "<< 1<< endl;
cout << endl;
}
int main()
{
int n;
cin >>n;
for(int i =0; i< n; i++)
{
int a;
cin >>a;
divide(a);
}
return 0;
}
|
- 筛质数
讲解
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
|
// 定理， 任意整数x 的倍数 2x 3x 等都不是质数
#include<bits/stdc++.h>
using namespace std;
const int N =1e6+11;
int primes[N], cnt;
int st[N];
// 朴素筛 O(nlogn) 这样的复杂度
void get_primes(int n)
{
for(int i =2; i<=n ; i++)
{
if(!st[i]) primes[cnt ++] =i;
// 是第一个质数倍数的，那么全部都置为 true，那么久无法访问了
for(int j =i +i; j<=n ; j+= i)
st[j] =true;
}
}
// 这种方法说实话，没有看懂
//线性筛选， 时间复杂度是 O(n)
void get_prime(int x) {
for(int i = 2; i <= x; i++) {
if(!st[i]) primes[cnt++] = i;
for(int j = 0; primes[j] <= x / i; j++) {
//对于任意一个合数x，假设pj为x最小质因子，当i<x/pj时，一定会被筛掉
st[primes[j]*i] = true;
if(i % primes[j] == 0) break;
/*
1.i%pj == 0, pj定为i最小质因子，pj也定为pj*i最小质因子
2.i%pj != 0, pj定小于i的所有质因子，所以pj也为pj*i最小质因子
*/
}
}
}
int main()
{
int n ;
cin >>n;
get_prime(n);
//get_primes(n);
cout << cnt<< endl;
return 0;
}
|
- AcWing 869. 试除法求约数
可以从实现的角度比较 合数和质数之间的差距。 首先在计算时候的初始化值是不同的，然后对于如何条件的 (x%i) 的处理也是不同的。
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
|
#include<bits/stdc++.h>
using namespace std;
vector<int> get_divisors(int x)
{
vector<int> res;
for(int i =1; i<= x/i; i++)
{
if(x %i ==0)
{
res.push_back(i); // 这里是一个细节，如果两个数字相同的话，那么只需要放进去一个，保证不重复
if(i != x/i) res.push_back(x /i);
}
}
sort(res.begin(), res.end());
return res;
}
int main()
{
int n ;
cin >>n;
for(int i =0; i< n; i++)
{
int tmp;
cin >>tmp;
vector<int> res =get_divisors(tmp);
for(auto u : res) cout << u<<" ";
cout << endl;
}
return 0;
}
|
求解约数个数和约数之和，就是理解下面的公式。有了上面求解约数的经验，那么下面这个应该不是很难。
1
2
3
|
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
|
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
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD =1e9+7;
// 因为 hash 是可以使用 first second 进行访问的，所以这个本质上也是一种键值对
unordered_map<int ,int> primes;
int main()
{
int n;
cin >>n;
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] ++;
}
// 对于这种可能有 int 溢出，所以使用long long 来进行表示
// 尤其是出现了 10^9 +7 取模，这种，说明数字很大，这个时候是需要使用long long 来表示结果的
ll ans =1;
for(auto item : primes) ans = ans*(item.second +1) %MOD;
cout << ans<< endl;
return 0;
}
|
求解最大公约数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include<bits/stdc++.h>
using namespace std;
int gcb(int a, int b)
{
return b ? gcb( b,a% b) :a;
}
int main()
{
int n ;
cin >>n;
while(n --)
{
int a, b;
cin >> a>>b;
cout << gcb(a, b)<< endl;
}
return 0;
}
|
快速幂
快速幂顾名思义，就是快速算某个数的多少次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。
时间复杂度是 $O(n)$ 优化成了 $O(logn)$. 所谓的快速幂，就是使用平方的方式，而不是一次次乘法进行处理。
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
|
#include<bits/stdc++.h>
using namespace std;
int fast_power(int a, int b, int p)
{
int res=1;
while(b)
{
if(b &1)// 这个表示奇数
res = 1ll* a*res %p;
// 这里体现的是 logn 的思想
a = 1ll* a* a %p;
b >>= 1;
}
return res;
}
int main()
{
int n;
cin >>n;
while(n--)
{
int a, b, p;
cin >>a>>b>>p;
printf("%d\n", fast_power(a, b, p));
}
return 0;
}
|