数论相关算法模板

欧几里得算法:GCD和LCM

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}

扩展欧几里得算法:

描述;设a,b不全为0,则存在整数x,y,使得:$gcd(a,b)=xa+y

int exgcd(int a,int b,int &x,int &y)
{
  if(b==0)
  {
      x=1;
      y=0;
      return a;
  }
  int r=exgcd(b,a%b,x,y);
  int t=x;
  x=y;
  y=t-a/b*y;
  return r;
}

说明:这里的返回值指的是$gcd(a,b)$的值,这个值一直没有改变,同时还求出了x和y.

素数筛法:

const int N=2000100;
int isprime[N];
void init()
{
    int i,j;
    isprime[1]=1;
    for(i=2; i<=sqrt(N); i++)
    {
        if(!isprime[i])
        {
            for(j=i+i; j<=N; j+=i)
                isprime[j]=1;
        }
    }
}

 

快速乘法:

ll q_mul(ll a,ll b)//计算a*b%mod的值
{
    ll ans=0;
    while(b)
    {
        if(b&1)
        {
            ans=(ans+a)%mod;
        }
        a=(a+a)%mod;
        b>>=1;
    }
    return ans;
}

快速幂:

int pow_mod(int a,int b,int c)
{
    a=a%c;
    int ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%c;
        a=a*a%c;
        b>>=1;
    }
    return ans;
}

 

快速排序:

#include <bits/stdc++.h>
using namespace std;
void quick_sort(int a[],int s,int e)
{
    if(s>=e) return ;
    int k=a[s];
    int i=s,j=e;
    while(i!=j)
    {
        while(j>i&&a[j]>=k) j--;
        swap(a[i],a[j]);
        while(i<j&&a[i]<=k) i++;
        swap(a[i],a[j]);
    }
    quick_sort(a,s,i-1);
    quick_sort(a,i+1,e);
}
int main()
{
    int a[]={7,1,3,8,12,11,2,9};
    quick_sort(a,0,7);
    for(int i=0;i<8;i++)
        printf("%d ",a[i]);
    return 0;
}

 

输入输出外挂

inline int read()
{
    int ret=0;
    char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while ('0'<=ch&&ch<='9')
    {
        ret=ret*10-48+ch;
        ch=getchar();
    }
    return ret;
}

快读2.0

namespace IO
{
const int MX = 4e7;
char buf[MX];
int c, sz;
void begin()
{
    c = 0;
    sz = fread(buf, 1, MX, stdin);
}
inline bool read(int &t)
{
    while(c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) c++;
    if(c >= sz) return false;
    bool flag = 0;
    if(buf[c] == '-') flag = 1, c++;
    for(t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; c++) t = t * 10 + buf[c] - '0';
    if(flag) t = -t;
    return true;
}
}
//使用的时候先IO::begin()
//然后输入时IO::read(x)

 

素数的线性筛法

const int N=1000+7;
ll  prime[N]= {1};
int pcnt=0;
int factor[N]= {1,1};
void Init_Prime()
{
    pcnt=1;
    for(ll i=2; i<N; i++)
    {
        if(!factor[i])
        {
            prime[pcnt++]=i;
            factor[i]=i;
        }
        for(ll j=1; j<pcnt&&i*prime[j]<N; j++)
        {
            factor[i*prime[j]]=prime[j];
            if(!(i%prime[j]))
                break;
        }
    }
    return;
}

组合数模板

int C(int n,int m)
{
    if(m<0 || m>n)
        return 0;
    int ans=1;
    for(int i=1; i<=m; ++i)
    {
        ans=ans*(n-m+i)/i;
    }
    return ans;
}
点赞
  1. riba2534说道:
    int gcd(int a,int b)
    {
        return !b?a:gcd(b,a%b);
    }
    

发表评论

电子邮件地址不会被公开。 必填项已用*标注