2020-10-15

Acwing模闆

雜七雜八

歸并排序

void merge_sort(int q[],int l,int r)
{
    if(l>=r) return;
    int mid = l+r >> 1;
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j]) tmp[k++]=q[i++];
        else tmp[k++]=q[j++];
    }
    
    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r) tmp[k++]=q[j++];
    
    for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
}
           

求逆序對

void merge_sort(int q[],int l,int r)
{
    if(l>=r) return;
    int mid = l+r >>1;
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j]) tmp[k++]=q[i++];
        else tmp[k++]=q[j++],ans+=mid-i+1;
    }
    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r) tmp[k++]=q[j++];
    
    for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
}
           

數論

線性篩求歐拉函數 O（N）

歐拉函數的應用

歐拉定理：當a與n互質時，a^ψ(n) mod n == 1

費馬定理（歐拉定理的特殊情況） a^(p-1) mod p == 1

#include<iostream>

using namespace std;
typedef long long ll;
const int N = 1e6+10;
int ol[N],pri[N],st[N],cnt;
void init(int n)
{
    ol[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            pri[cnt++]=i;
            ol[i]=i-1;
        }
        for(int j=0;pri[j]<=n/i;j++)
        {
            st[pri[j]*i]=1;
            if(i%pri[j]==0)
            {
                ol[i*pri[j]]=ol[i]*pri[j];
                break;
            }
            ol[i*pri[j]]=ol[i]*(pri[j]-1);
        }
    }
}

int main()
{
    int n;
    scanf("%d",&n);
     
    init(n);
    ll res=0;
    for(int i=1;i<=n;i++) res+=ol[i];
    printf("%lld\n",res);
    return 0;
}
           

快速幂

#include<iostream>

using namespace std;
typedef long long ll;
int kmi(int a,int b,int p)
{
    ll res=1%p;
    while(b)
    {
        if(b&1) res=res*a%p;
        b>>=1;
        a=a*1ll*a%p;
    }
    return res;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,b,p;
        scanf("%d%d%d",&a,&b,&p);
        printf("%d\n",kmi(a,b,p));
    }
    return 0;
}
           

快速幂應用 快速幂求逆元

#include<iostream>

using namespace std;
typedef long long ll;
int kmi(int a,int b,int p)
{
    ll res = 1;
    while(b)
    {
        if(b&1) res=res*a%p;
        b>>=1;
        a=a*1ll*a%p;
    }
    return res;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,p;
        scanf("%d%d",&a,&p);
        
        if(a%p==0) puts("impossible");
        
        else printf("%d\n",kmi(a,p-2,p));
    }
    return 0;
}
           

歐幾裡得算法(求最大公約數)

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
           

擴充歐幾裡得算法

給定n對正整數ai,bi，對于每對數，求出一組xi,yi，使其滿足ai∗xi+bi∗yi=gcd(ai,bi)

#include<iostream>

using namespace std;
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;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,b,x,y;
        scanf("%d%d",&a,&b);
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}