质数/素数:一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数
约数:约数,又称因数。整数a除以整数b(b≠0)除得的商正好是整数而没有余数,我们就说a能被b整除,或b能整除a。a称为b的倍数,b称为a的约数
日期
#include <iostream>
using namespace std;
int months[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
// 判断日期的合法性
bool check_valid(int date) //形如20210305
{
int year = date / 10000;
int month = date % 10000 / 100;
int day = date % 100;
if (month <= 0 || month >= 13) return false;
if (day == 0 || month != 2 && day > months[month]) return false;
if (month == 2)
{
int leap = (year % 4 == 0 && year % 100 != 0 || year % 400 == 0);
if (day > 28 + leap) return false;
}
return true;
}
// 得到某年某月的天数
int get(int year, int month)
{
if (month != 2) return months[month];
else
{
// 2月
int leap = (year % 4 == 0 && year % 100 != 0 || year % 400 == 0);
return 28 + leap;
}
}
// 判断两个日期之间有多少个回文日期
int get(int date1, int date2, int k) //k使函数签名不同从而编译通过
{
int ans = 0;
for (int i = 1000; i < 10000; i++)
{
int date = i, x = i;
for (int j = 0; j < 4; j++) date = date * 10 + x % 10, x /= 10; //根据年份构造出回文日期
if (date1 <= date && date <= date2 && check_valid(date)) ans++;
}
return ans;
}
// 给定年月日,经过n天后对应的日期
void pass(int y, int m, int d, int n)
{
while (n--)
{
d++;
if (d > get(y, m)) m++, d = 1;
if (m > 12) y++, m = 1;
}
printf("%d-%02d-%02d\n", y, m, d);
}
bool is_leap(int a)
{
if ((0 == a % 4 && a % 100 != 0) || (0 == a % 400)){
return true;
}
return false;
}
1
模的性质
余数的和等于和的余数:a%p+b%p=(a+b)%p
余数的差等于差的余数:a%p-b%p=(a-b)%p
余数的积等于积的余数: a%p * b%p=(a*b)%p
2
ab互质的充要条件是xa+yb=1有整数解
3
ab的最大公约数d,ab是整数,若gcd(a,b)=d,ax+by中x y ax+by都是d的整数倍
ax+by=d;
拓展欧几里得算法可以算出x和y;
求一个数的约数
//扩展欧几里得
int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1; y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a/b) * x;
return d;
}
//求约数个数
vector<int> div(int n) {
vector<int> ans;
for (int i = 1; i <= n / i; i ++) {
if (n % i == 0) {
ans.push_back(i);
if (i != n / i) ans.push_back(n / i); // 注意边界情况,有可能出现 n/i == i的情况导致重复加入数值
}
}
sort(ans.begin(), ans.end());
return ans;
}
//最大公约数
int fun(int m,int n){
int rem; //余数,当余数为0的时候,最后的m即为最大公约数
//先用较小的数对较大的数取余,再用余数对较小的数求余,直到余数为零
while(n > 0){
rem = m % n;
m = n;
n = rem;
}
return m; //将结果返回
}
4
快速幂
求 m^k mod p,时间复杂度 O(logk)。
int qmi(int m, int k, int p)
{
int res = 1 % p, t = m;
while (k)
{
if (k&1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}
5
求取最大公约数
int gcd(int a,int b){
if(b==0)
return a;
return gcd(b,a%b);
}
6
求最小公倍数
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
7
获取质数,且获取每个数的最小质因子
使用时直接调用get_primes 传入上限即可
int primes[N],cnt;
int minprimes[N];
bool st[N];
void get_primes(int n){
for(int i=2;i<=n;i++){
if(!st[i]) minprimes[i]=i,primes[cnt++]=i;
for(int j=0;primes[j]*i<n;j++){
st[primes[j]*i]=true;
minprimes[primes[j]*i]=primes[j];
if(i%primes[j]==0) break;
}
}
}
8
spfa最短路
#include<queue>
#define v first
#define w second
using namespace std;
typedef pair<int,int> pii;
int inq[N],d[N];//d为结果
vector<pii> E[N];
void spfa(){
memset(d,0x3f,sizeof d);
memset(inq,0,sizeof inq);
queue<int> q;
q.push(1);
d[1]=0;
inq[1]=1;
while(q.size()){
int now=q.front();
q.pop();
inq[now]=0;
for(int i=0;i<E[now].size();i++){
int vv=E[now][i].v;
if(d[vv]>d[now]+E[now][i].w){
d[vv]=d[now]+E[now][i].w;
if(inq[vv]) continue;
inq[vv]=1;
q.push(vv);
}
}
}
}
9
prim最小生成树
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e3+10,INF=0x3f3f3f3f;
int dist[N],g[N][N];//dist 点到集合的最短距离 g使用要先初始化memset(g,0x3f,sizeof(g))
bool st[N];
int n,m;
//返回最小树长度
int prim(){
int res=0;
memset(st,0,sizeof(st));
memset(dist,0x3f,sizeof(dist));
dist[1]=0;
for(int i=1;i<=n;i++){
int id=-1,c_dist=INF;
for(int j=1;j<=n;j++){
if(!st[j]&&dist[j]<c_dist){
id=j;
c_dist=dist[j];
}
}
st[id]=true;
res+=c_dist;
for(int j=1;j<=n;j++){
if(!st[j]){
dist[j]=min(dist[j],g[id][j]);
}
}
}
return res;
}
10
背包
01背包
转移方程
dp[i][j]表示在i物品时有装了j重的东西
w[i]重量,v[i]价值
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
完全背包 物品数量无上限
dp[i][j]
for(int k=0;k*w[i]<=j;k++){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i])
}
多重背包 物品数量有上限
limit[i]物品数量上限
dp[i][j]
for(int k=0;k<limit[i]&&k*w[i]<=j;k++){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i])
}
11
// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )
for (int j = 0; j <= i; j ++ )
if (!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
12树状数组
#include<iostream>
using namespace std;
const int N = 1e5+10;
int nums[N],temp[N];
int max_size=N;
int n;
int lowbit(int x){
return x&-x;
}
int sum(int l){
int res=0;
for(int i=l;i;i-=lowbit(i))
res+=nums[i];
return res;
}//求0到l的和
void add(int x,int v){
for(int i=x;i<=max_size;i+=lowbit(i))
nums[i]+=v;
}//插入
12
二分
while(l<r){
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
while(l<r){
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
13
区间合并
// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first)
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res;
}
14
线段树
//n为数组长度,m为操作次数,nums为数组
#include<iostream>
using namespace std;
const int N= 1e5+10;
int nums[N];
struct node{
int l,r;
int sum;
}tr[4*N];
int n,m;
void push_up(int v){
tr[v].sum=tr[v<<1].sum+tr[v<<1|1].sum;
}
int getsum(int u,int l,int r){
if(l<=tr[u].l&&r>=tr[u].r) return tr[u].sum;
int mid=tr[u].l+tr[u].r>>1;
int res=0;
if(l<=mid)
res+=getsum(u<<1,l,r);
if(r>=mid+1)
res+=getsum(u<<1|1,l,r);
return res;
}
void modify(int v,int u,int c){
if(tr[v].l==tr[v].r) tr[v].sum+=c;
else{
int mid=tr[v].l+tr[v].r>>1;
if(u<=mid){
modify(v<<1,u,c);
}else{
modify(v<<1|1,u,c);
}
push_up(v);
}
}
void build(int v,int l,int r){
if(l==r) tr[v]={l,r,nums[r]};
else{
tr[v]={l,r};
int mid=l+r>>1;
build(v<<1,l,mid);build(v<<1|1,mid+1,r);
push_up(v);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%d",&nums[i]);
}
build(1,1,n);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(a){
modify(1,b,c);
}else{
printf("%d\n",getsum(1,b,c));
}
}
}
15
并查集
void init(){
for(int i=0;i<n;i++){
nums[i]=i;
}
}
int find(int i){
if(nums[i]==i){
return i;
}else{
nums[i]=find(nums[i]);
return nums[i];
}
}
void merage(int i,int j){
nums[find(i)]=find(j);
}
16
全排列
#include<iostream>
using namespace std;
const int N = 10;
int path[N];//保存序列
int state[N];//数字是否被用过
int n;
void dfs(int u)
{
if(u > n)//数字填完了,输出
{
for(int i = 1; i <= n; i++)//输出方案
cout << path[i] << " ";
cout << endl;
}
for(int i = 1; i <= n; i++)//空位上可以选择的数字为:1 ~ n
{
if(!state[i])//如果数字 i 没有被用过
{
path[u] = i;//放入空位
state[i] = 1;//数字被用,修改状态
dfs(u + 1);//填下一个位
state[i] = 0;//回溯,取出 i
}
}
}
int main()
{
cin >> n;
dfs(1);
return 0;
}
114514