*一定要注意 数组最大开1e6*
快速幂模板

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
int a,k,p;
int qsm(int a,int k,int p)
{
    LL res = 1%p; //当a=1,p=1,k等于0时的特殊情况要%p
    while(k)
    {
        if(k & 1) res = res*a%p; //把每次有效位的结果累乘mod p
        k >>= 1; 
        a = (LL)a*a%p; 
    }
    return res;
}
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d%d",&a,&k,&p);
        printf("%d\n",qsm(a,k,p));
    }
    return 0;
}

统计质因子的个数

//朴素版判断n是否为质数o(n)
//优化1 一个数的约数是成对出现的 因此每次只枚举一半 一半长位根号n
//试除法判断质数 时间复杂度为根号n
bool is_prime(int n)
{
    if(n<2) return false;
    //注意这里一定是等于,因为中间可能是约数
    //用sqrt太慢 用i*i可能溢出 推荐使用i<=n/i
    for(int i=2;i<=n/i;i++)
    {
        if(n%i == 0)
            return false;
    }
    return true;
}

//试除法 统计质因数的个数
//优化  n最多只是包含一个大于根号n的质因子
for(int i=2,cnt=0;i*i<=n;i++)
{
    if(n%i == 0) //这里能够确保i一定是质数(因为下一个满足循环的n一定是质数)
    {
        while(n%i == 0)
        {
            n /= i; //将i的倍数全部从n中删除
        }
        cnt++;
    }
}
if(n > 1) cnt++;

欧拉函数求1-n中(包括n)与n互为质数的个数

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
int main()
{
    cin>>n;
    //要用欧拉函数求1至n的互质数的个数,首先要求n的质因子
    LL res = n; //初始值为n
    for(int i=2;i*i<=n;i++)
    {
        if(n % i == 0) //i一定是质因子
        {
            res = res / i * (i-1);  //为了避免小数,这里用除法
            while(n%i == 0)
                n /= i;
        }
    }
    if(n > 1) res = res / n * (n-1);
    cout<<res<<endl;
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20010,M =26;
int cnt[M][M];
string s;
bool st[M][M];
int n,m;
void update(int l,int r,int v)
{
    l = max(0,l);
    r = min(r,n-1);
    for(int i=l;i+2<=r;i++)
    {
        char a = s[i],b = s[i+1],c = s[i+2];
        if(a != b && b == c)
        {
            cnt[a][b] += v;
            if(cnt[a][b] >= m) st[a][b] = true;
        }
    }
}
int main()
{
    cin>>n>>m>>s;
    for(int i=0;i<s.size();i++) s[i] -= 'a';
    update(0,n-1,1);
    for(int i=0;i<n;i++)
    {
        char t = s[i];
        update(i-2,i+2,-1);
        for(int j=0;j<26;j++)
        {
            if(j != t)
            {
                s[i] = j;
                update(i-2,i+2,1);
                update(i-2,i+2,-1);
            }
        }
        s[i] = t;
        update(i-2,i+2,1);
    }
    int res = 0;
    for(int i=0;i<26;i++)
        for(int j=0;j<26;j++)
            if(st[i][j])
                res++;
    cout<<res<<endl;
    for(int i=0;i<26;i++)
        for(int j=0;j<26;j++)
            if(st[i][j])
                printf("%c%c%c\n",i+'a',j+'a',j+'a');
    return 0;
}

吃蛋糕

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 500010;
typedef long long LL;
int T,n;
LL s[N];
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        LL res = 1e18;; 
        int l = n/2 + 1;
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            s[i] = s[i-1] + x;
            if(i >= l) res = min(res,s[i]-s[i-l]);
        }
        cout<<res<<' '<<s[n] - res<<endl;
    }
    return 0;
}

抽取后满组abb,先枚举bb型

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n;
int w[N],l[N],r[N];
int main()
{
    cin>>n;
    int cnt = 0;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        l[w[i]]++;
        if(l[w[i]] == 1) cnt++;
    }
    LL res = 0;
    for(int i=n;i;i--)
    {
        l[w[i]]--;
        r[w[i]]++;
        if(l[w[i]] == 0) cnt--;
        if(r[w[i]] == 2){
            res += cnt;
            if(l[w[i]] != 0)
                res--;
        }
    }
    cout<<res<<endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 7510;
int a[N],b[N],ans[N];
int n,cnt;
int main()  
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++)
    {
        if(a[i] == b[i])
            cnt++;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<2;j++)
        {
            int sum = cnt;
            for(int l=i,r=i+j;l>=1&&r<=n;l--,r++) //枚举的所有区间数
            {
                if(a[l] == b[l]) sum--; //要把该区间内本身匹配的数减掉
                if(a[r] == b[r]) sum--;
                if(a[l] == b[r]) sum++;
                if(a[r] == b[l]) sum++;
                ans[sum]++;  //统计该匹配数的个数
            }
        }
    }
    for(int i=0;i<=n;i++)
        cout<<ans[i]<<endl;
    return 0;
}

//转化为区间覆盖的问题
/*
问题分析：
当天数为r时，1头感染的牛在经过若干天后可以扩展到2r+1长度的区间，
不同牛可以重复感染，所以原始感染数为区间长度ci/2r+1上取整
可以发现，当r越大时，小区间长度越大，此时覆盖的区间段数就越小，原始感染数就越小
但是区间也不能无限大，这里分为三种情况讨论
1.Ci取中间部分0111..110  此时有2r+1<=Ci 及r<=(Ci-1)/2下取整
2.Ci取左右边界111..10  此时有 r<=Ci-1
两个部分取交集 及r = min(情况1,情况2)
3.当区间全为1时候，则一定可以由一头奶牛经过至少n-1天得到
*/
//小技巧 如何求a/b上取整 --> 可以转化为(a+b-1)/b下取整数
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 3*1e5 + 10;
char s[N]; //用来存最后感染的序列
int n;
vector<int> cnt; //因为不知道具体每个区间长度是多少,所以用动态数组
int main()
{
    scanf("%d%s",&n,s);
    int r = n; //因为后面要求情况1和2的交集(即较小值),所以这里取一个最大天数情况
    for(int i=0;i<n;i++)
    {
        if(s[i] == '0') continue;
        int j = i+1; //j从第一个边界的下一个位置开始
        while(j<n && s[j] == '1') j++; //找这个区间的长度
        int c = j - i; //c表示该区间的长度
        int d = (c-1) / 2; //默认为中间区间的情况
        if(!i || j == n) d = c - 1; //如果为左右边界的情况
        r = min(r,d); //取一个公共满足的最大天数r
        cnt.push_back(c); //将该区间加进来
        i = j; //i开始扫描下一个最大区间
    }
    int res = 0;
    if(cnt.size() == 1) //全为1的情况
    {
        cout<<1<<endl;
        return 0;
    }
    for(int c:cnt) //迭代求和每个区间可以分为多少个2r+1子区间,要向上取整
    {
        res += (c+2*r) / (2*r+1);
    }
    printf("%d\n",res);
    return 0;
}

破环成链

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 4*1e5 + 10;
int T,n,m;
LL s[N];
LL a[N];
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            a[i] %= m;
        }
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++) a[n+i] = a[i] + m;
        for(int i=1;i<=2*n;i++) s[i] = s[i-1] + a[i];
        LL res = 1e18;
        for(int l=1;l<=n;l++)
        {
            int r = l + n - 1;
            int p = l + r >> 1;
            LL left = (p-l+1)*(LL)a[p] - (s[p]-s[l-1]);
            LL right = (s[r]-s[p]) - (r-p)*(LL)a[p];
            res = min(res,left+right);
        }
        cout<<res<<endl;
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;
typedef long long LL;
LL a[N],b[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int j=1;j<=m;j++) cin>>b[j];

    for(int i=1;i<=m;i++)
    {
        int t = 0; //表示每次吃的糖果的长度
        for(int j=1;j<=n;j++)
        {
            if(a[j] <= t) continue; //注意t这个糖果也被吃掉了
            int eat = min(b[i],a[j]) - t;
            a[j] += eat;
            t += eat;
            if(t == b[i]) break; //当糖果已经吃完时候，直接退出
        }
    }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<endl;
    return 0;
}