快速幂
#include<bits/stdc++.h>
using namespace std;
unsigned long long a,b,k,ans=1;
int main(){
cin>>a>>b>>k;
if(b==0){
ans=1%k;
cout<<ans<<endl;
return 0;
}while(b!=0){
if(b&1)
ans=ans*a%k;
a=a*a%k;
b>>=1;
}cout<<ans<<endl;
return 0;
}
64 位整数乘法
#include<bits/stdc++.h>
using namespace std;
unsigned long long a,b,k,ans;
int main(){
cin>>a>>b>>k;
while(b!=0){
if(b&1)
ans=(ans+a)%k;
a=a*2%k;
b>>=1;
}cout<<ans<<endl;
return 0;
}
求质数（线性筛）
#include<bits/stdc++.h>
using namespace std;
unsigned long long cnt,ans,prime[80000050],n;
bool f[80000050];
void ffind(unsigned n){
for(unsigned long long i=2;i<=n;i++){
if(f[i]==0){
ans+=i;
prime[cnt++]=i;
}for(unsigned long long j=0;prime[j]<=n/i;j++){
f[prime[j]*i]=1;
if(i%prime[j]==0)
break;
}
}return ;
}int main(){
cin>>n;
ffind(n);
cout<<ans<<endl;
return 0;
}
【模板】唯一分解定理
#include<bits/stdc++.h>
using namespace std;
unsigned long long n;
int main(){
cin>>n;
for(unsigned long long i=2;i*i<=n;i++){
int cnt=0;
if(n%i==0){
cout<<i<<"^";
while(n%i==0){
n/=i;
cnt++;
}cout<<cnt<<endl;
}
}if(n>1)
cout<<n<<"^1";
return 0;
}
【模板】求单个欧拉数
#include<bits/stdc++.h>
using namespace std;
unsigned long long n;
int main(){
while(1){
cin>>n;
if(n==0)
return 0;
unsigned long long res=n;
for(unsigned long long i=2;i*i<=n;i++){
if(n%i==0){
res=res/i*(i-1);
while(n%i==0)
n/=i;
}
}if(n>1)
res-=res/n;
cout<<res<<endl;
}return 0;
}
区间最大值
#include<bits/stdc++.h>
using namespace std;
int n,m,st[100020][25],x,y;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>st[i][0];
for(int j=1;j<=log2(n);j++){
for(int i=1;i+(1<<j)-1<=n;i++)
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}for(int i=1;i<=m;i++){
cin>>x>>y;
int k=log2(y-x+1);
cout<<max(st[x][k],st[y-(1<<k)+1][k])<<endl;
}return 0;
}
「模板」树状数组
#include<cstdio>
int n,m,c[10000020],x,y,z;
inline int lowbit(int x){
return x&-x;
}inline int sum(int x){
int ans=0;
for(int i=x;i>=1;i-=lowbit(i))
ans+=c[i];
return ans;
}inline void updata(int x,int val){
for(int i=x;i<=n;i+=lowbit(i))
c[i]+=val;
return ;
}int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&z);
updata(i,z);
}for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
if(x==0)
printf("%d\n",sum(z)-sum(y-1));
else
updata(y,z);
}return 0;
}
求逆序对数目
#include<bits/stdc++.h>
using namespace std;
long long num,c[5000020],cnt=-1,ccnt,flag[5000020],ans;
struct node{
long long val;
int place;
}a[100020];
bool cmp(node a,node b){
return a.val<b.val;
}int lowbit(int x){
return x&-x;
}long long sum(int x){
long long ans=0;
for(int i=x;i>=1;i-=lowbit(i))
ans+=c[i];
return ans;
}void updata(int x){
for(int i=x;i<=num;i+=lowbit(i))
c[i]++;
return ;
}int main(){
cin>>num;
for(int i=1;i<=num;i++){
cin>>a[i].val;
a[i].place=i;
}sort(a+1,a+1+num,cmp);
for(int i=1;i<=num;i++){
if(a[i].val!=cnt){
cnt=a[i].val;
a[i].val=++ccnt;
}else
a[i].val=ccnt;
}for(int i=1;i<=num;i++)
flag[a[i].place]=a[i].val;
for(int i=num;i>=1;i--){
updata(flag[i]);
ans+=sum(flag[i]-1);
}cout<<ans<<endl;
}
【模板】树状数组 2
#include<bits/stdc++.h>
using namespace std;
int n,m,a[500020],c[500020],x,y,z,k;
int lo(int x){
return x&-x;
}void up(int x,int v){
for(int i=x;i<=n;i+=lo(i))
c[i]+=v;
}int su(int x){
int ans=0;
for(int i=x;i>0;i-=lo(i))
ans+=c[i];
return ans;
}int f(int x){
int l=1,r=n,mid;
while(l<=r){
mid=(l+r)>>1;
int s=su(mid);
if(s>=x/2+1)
r=mid-1;
else
l=mid+1;
}return c[l];
}int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
up(i,a[i]-a[i-1]);
}for(int i=1;i<=m;i++){
cin>>x;
if(x==1){
cin>>y>>z>>k;
up(y,k);
up(z+1,-k);
}if(x==2){
cin>>y;
cout<<su(y)<<endl;
}
}return 0;
}
树状数组 3 ：区间修改，区间查询
#include<bits/stdc++.h>
using namespace std;
long long c1[1000010],c2[1000010],n,m,flag,a,b,k,last;
inline long long lowbit(long long x){
return x &-x;
}inline void updata1(long long x,long long val){
for(long long i=x;i<=n;i+=lowbit(i))
c1[i]+=val;
return ;
}inline void updata2(long long x,long long val){
for(long long i=x;i<=n;i+=lowbit(i))
c2[i]+=val;
return ;
}inline long long sum1(long long x){
long long ans=0;
for(long long i=x;i>=1;i-=lowbit(i))
ans+=c1[i];
return ans;
}inline long long sum2(long long x){
long long ans=0;
for(long long i=x;i>=1;i-=lowbit(i))
ans+=c2[i];
return ans;
}int main(){
cin>>n>>m;
for(long long i=1;i<=n;i++){
cin>>a;
updata1(i,a-last);
updata2(i,(a-last)*(i-1));
last=a;
}for(long long i=1;i<=m;i++){
cin>>flag>>a>>b;
if(flag==1){
cin>>k;
updata1(a,k);
updata1(b+1,-k);
updata2(a,k*(a-1));
updata2(b+1,-k*b);
}else
cout<<b*sum1(b)-(a-1)*sum1(a-1)-sum2(b)+sum2(a-1)<<endl;
}return 0;
}
区间求和与区间增加
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[400020],lazy[400020],s[400020],n,m;
void updata(ll k,ll lleft,ll rright){
if(lazy[k]){
lazy[k*2]+=lazy[k];
lazy[k*2+1]+=lazy[k];
ll mid=(lleft+rright-1)/2;
s[k*2]+=lazy[k]*(mid-lleft+1);
s[k*2+1]+=lazy[k]*(rright-mid);
lazy[k]=0;
}return ;
}void make(ll lleft,ll rright,ll l,ll r,ll val,ll x){
if(l==lleft&&r==rright) {
lazy[x]+=val;
s[x]+=val*(r-l+1);
return ;
}if(l==r)
return ;
updata(x,l,r);
ll mid=(l+r-1)>>1;
if(rright<=mid)
make(lleft,rright,l,mid,val,x<<1);
else{
if(lleft>mid)
make(lleft,rright,mid+1,r,val,x*2+1);
else{
make(lleft,mid,l,mid,val,x*2);
make(mid+1,rright,mid+1,r,val,x*2+1);
}
}s[x]=s[x<<1]+s[x*2+1];
return ;
}void build(ll lleft,ll rright,ll x){
if(lleft==rright){
s[x]=a[lleft];
return ;
}ll mid=(lleft+rright-1)/2;
build(lleft,mid,x*2);
build(mid+1,rright,x*2+1);
s[x]=s[x*2]+s[x*2+1];
return ;
}ll sum(ll lleft,ll rright,ll l,ll r,ll k){
if(lleft==l&&rright==r)
return s[k];
updata(k,l,r);
ll mid=(l+r-1)/2;
if(rright<=mid)
return sum(lleft,rright,l,mid,k*2);
if(lleft>mid)
return sum(lleft,rright,mid+1,r,k*2+1);
return sum(lleft,mid,l,mid,k*2)+sum(mid+1,rright,mid+1,r,k*2+1);
} main(){
cin>>n>>m;
for(ll i=1;i<=n;i++)
cin>>a[i];
build(1,n,1);
for(ll i=1;i<=m;i++){
char a;
cin>>a;
if(a=='C'){
ll x,y,k;
cin>>x>>y>>k;
make(x,y,1,n,k,1);
}else{
ll x,y;
cin>>x>>y;
cout<<sum(x,y,1,n,1)<<endl;
}
}return 0;
}
单点更改与区间最大值
#include<bits/stdc++.h>
using namespace std;
int n,a[500010],s[8000100],m;
void b(int k,int l,int r) {
if(l==r) {
s[k]=a[l];
return;
}
int mid=(l+r)/2;
b(2*k,l,mid);
b(2*k+1,mid+1,r);
s[k]=max(s[k*2],s[k*2+1]);
}void add(int k,int l,int r,int x,int v) {
if(l==r&&l==x) {
s[k]=v;
return;
}
if(x<l||x>r)
return;
int mid=(l+r)/2;
if(l<=x&&x<=mid)
add(k*2,l,mid,x,v);
if(mid+1<=x&&x<=r)
add(k*2+1,mid+1,r,x,v);
s[k]=max(s[k*2],s[k*2+1]);
}int sum(int k,int l,int r,int x,int y) {
if(y<l||x>r)
return 0;
if(x<=l&&r<=y)
return s[k];
int mid=(l+r)/2;
return max(sum(k*2,l,mid,x,y),sum(k*2+1,mid+1,r,x,y));
}int main() {
cin>>n>>m;
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
b(1,1,n);
char f;
int x,y;
for(int i=1;i<=m;i++){
cin>>f>>x>>y;
if(f=='U')
add(1,1,n,x,y);
else
printf("%d\n",sum(1,1,n,x,y));
}return 0;
}
前缀统计
#include<bits/stdc++.h>
using namespace std;
int tree[5000050][26],id,nodes,n,ans;
void insert(string str){
int p=0;
for(int i=0;str[i];i++){
if(tree[p][str[i]-'a']==0)
tree[p][str[i]-'a']=++nodes;
p=tree[p][str[i]-'a'];
}
}int add(string str){
int p=0;
for(int i=0;str[i];i++){
if(tree[p][str[i]-'a']==0)
return 0;
p=tree[p][str[i]-'a'];
}return 1;
}
int main(){
string str;
cin>>str>>n;
insert(str);
for(int i=1;i<=n;i++){
cin>>str;
ans+=add(str);
}cout<<ans<<endl;
return 0;
}
Dijkstra
#include<bits/stdc++.h>
using namespace std;
struct node{
int k,num;
friend bool operator < (const node & a,const node & b){
return a.num>b.num;
}
}top;
priority_queue<node> q;
vector<node> v[100005];
int n,m,s,dis[100005];
bool vis[100005];
int main(){
cin>>n>>m>>s;
for(int i=1,a,b,c;i<=m;i++){
cin>>a>>b>>c;
v[a].push_back({b,c});
}memset(dis,0x3f,sizeof(dis));
dis[s]=0;
q.push({s,0});
while(q.empty()==0){
top=q.top();
q.pop();
if(vis[top.k]==1)
continue;
vis[top.k]=1;
for(node i:v[top.k]){
if(i.num+top.num<dis[i.k]){
dis[i.k]=i.num+top.num;
q.push({i.k,dis[i.k]});
}
}
}for(int i=1;i<=n;i++){
if(dis[i]!=0x3f3f3f3f)
cout<<dis[i]<<endl;
}return 0;
}
Kruskal
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,ans,fa[114514];
struct node{
int x,y,val;
}a[114514];
bool cmp(node a,node b){
return a.val<b.val;
}int find_root(int x){
if(x==fa[x])
return x;
return find_root(fa[x]);
}int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[++m].val;
a[m].x=i;
a[m].y=j;
}
}sort(a+1,a+1+m,cmp);
for(int i=1;i<=114513;i++){
fa[i]=i;
}for(int i=1;i<=m;i++){
int x=find_root(a[i].x),y=find_root(a[i].y);
if(x!=y){
fa[max(x,y)]=min(x,y);
cnt++;
ans+=a[i].val;
}
}cout<<ans<<endl;
return 0;
}
prim
#include<bits/stdc++.h>
using namespace std;
int n, m, dis[MAXN], MST; // dis[i]表示与i相连的最短路径
bool vis[MAXN]; // vis[i] 为i是否加入最小生成树
struct edge {
int to, tot; // to为终点,tot为边权
bool operator < (const edge &a) const {
return tot > a.tot; // 按照边权从小到大排序
}
};
vector <edge> g[MAXN];
void Prim() {
memset(dis, 0x3f, sizeof(dis));
memset(vis, false, sizeof(vis));
dis[1] = 0; // 初始化
priority_queue <edge> q;
q.push(edge({1, 0}));
while (!q.empty()) {
int x = q.top().to;
q.pop();
if (vis[x]) continue;
vis[x] = true;
for (int i = 0; i < g[x].size(); i++) {
int v = g[x][i].to, tot = g[x][i].tot;
if (!vis[v] && dis[v] > tot) {
dis[v] = tot; // 将距离最近的结点加入到最小生成树中
q.push(edge({v, dis[v]}));
}
}
MST += dis[x];
}
return;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
g[x].push_back(edge({y, z}));
g[y].push_back(edge({x, z}));
}
Prim();
printf("%d", MST);
return 0;
}
floyd
#include <iostream>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int main()
{
int a[21][21],m,n,i, j, w;
for (int i = 1; i <= 20; i++) {
for (int j = 1; j <= 20; j++) {
if (i == j) {a[i][j] = 0;}
else a[i][j] = INF;
}
}
cin>>n>>m;
for (int k = 1;k<= m;k++) {
cin>>i>>j>>w;
a[i][j] = w;
a[j][i] = w;
}
for (int p = 1; p <= n; p++) {
for (int i = 1; i <= n; i++) {
if (a[i][p] == INF) continue;
for (int j = 1; j <= n; j++) {
if (i==j)continue;
a[i][j] = min(a[i][j], a[i][p] + a[p][j]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,m,k,dis[50005],ans=0x3f3f3f3f;
struct node{
int k,num;
friend bool operator < (const node a,const node b){
return a.num>b.num;
}
}top;
vector<node> v[50005];
priority_queue<node> q;
bool vis[10000];
int main(){
cin>>n>>m>>k;
for(int i=1,a,b,c;i<=m;i++){
cin>>a>>b>>c;
v[a].push_back({b,c});
v[b].push_back({a,c});
for(int j=1;j<=k;j++){
v[a+n*(j-1)].push_back({b+n*j,c/2});
v[b+n*(j-1)].push_back({a+n*j,c/2});
v[b+n*j].push_back({a+n*j,c});
v[a+n*j].push_back({b+n*j,c});
}
}memset(dis,0x3f,sizeof(dis));
dis[1]=0;
q.push({1,0});
while(!q.empty()){
top=q.top();
q.pop();
for(node i:v[top.k]){
if(i.num+top.num<dis[i.k]){
dis[i.k]=i.num+top.num;
q.push({i.k,dis[i.k]});
}
}
}for(int i=0;i<=k;i++)
ans=min(ans,dis[(i+1)*n]);
cout<<ans<<endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int cnt,dis[20001][50],t,vis[20001][50],n,m,k,ans=0x3f3f3f3f;
struct node{
long long k,num,sum;
friend bool operator < (const node a,const node b){
return a.num>b.num;
}
}top;
priority_queue<node> q;
vector<node> v[50005];
int main(){
cin>>n>>m>>k;
for(long long i=1,a,b,c;i<=m;i++){
cin>>a>>b>>c;
v[a].push_back({b,c});
v[b].push_back({a,c});
}memset(dis,0x3f,sizeof(dis));
dis[1][0]=0;
q.push({1,0,0});
while(!q.empty()){
top=q.top();
q.pop();
vis[top.k][top.sum]=1;
for(node i:v[top.k]){
if(dis[top.k][top.sum]+i.num/2<dis[i.k][top.sum+1]&&vis[i.k][top.sum+1]==0&&top.sum<k){
dis[i.k][top.sum+1]=dis[top.k][top.sum]+i.num/2;
q.push({i.k,dis[i.k][top.sum+1],top.sum+1});
}if(dis[top.k][top.sum]+i.num<dis[i.k][top.sum]&&vis[i.k][top.sum]==0){
dis[i.k][top.sum]=dis[top.k][top.sum]+i.num;
q.push({i.k,dis[i.k][top.sum],top.sum});
}
}
}for(long long i=0;i<=k;i++)
ans=min(ans,dis[n][i]);
cout<<ans;
return 0;
}
SPFA
#include<bits/stdc++.h>
using namespace std;
struct node{
int k,num;
};
vector<node> v[10005];
int n,m,s,dis[10005],tot[10005];
bool vis[10005];
queue<int> q;
void spfa(){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(s);
dis[s]=0;
vis[s]=1;
tot[s]++;
while(!q.empty()){
int top=q.front();
q.pop();
vis[top]=0;
for(node i:v[top]){
if(dis[i.k]>dis[top]+i.num){
dis[i.k]=dis[top]+i.num;
if(vis[i.k]==0){
q.push(i.k);
vis[i.k]=1;
tot[i.k]++;
if(tot[i.k]>n){ //负权环
printf("-1\n");
exit(0);
}
}
}
}
}return ;
}int main(){
cin>>n>>m>>s;
for(int i=1,a,b,c;i<=m;i++){
cin>>a>>b>>c;
v[a].push_back({b,c});
}spfa();
for(int i=1;i<=n;i++){
if(dis[i]!=0x3f3f3f3f)
cout<<dis[i]<<endl;
}return 0;
}
差分约束系统
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m,tot,cnt[1010];
int dis[1010],vis[1010];
struct node{
int k,num;
};
vector<node> v[1010];
bool SPFA(int s){
queue<int> q;
memset(dis,0xcf,sizeof(dis)),memset(vis,0,sizeof(vis)),memset(cnt,0,sizeof(cnt));
dis[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty()){
int top=q.front();
q.pop();
vis[top]=0;
for(node i:v[top]){
int v=i.k;
if(dis[v]>dis[top]+i.num){
dis[v]=dis[top]+i.num;
if(!vis[v]){
q.push(v);
vis[v]=1;
cnt[v]++;
if(cnt[v]>n)
return 0;
}
}
}
}return 1;
}int main(){
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1,a,b,c;i<=m;++i){
cin>>a>>b>>c;
v[a-1].push_back({b,c});
v[b].push_back({a-1,-c});
}bool flag=1;
for(int i=0;i<=n;++i)
if(!SPFA(i)) {flag=0; break;}
if(flag)
cout<<"true"<<endl;
else
cout<<"false"<<endl;
for(int i=0;i<=m+1;i++)v[i].erase(v[i].begin(),v[i].end());
}return 0;
}