基础数论

GCD相关

GCD

ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a%b);
}

EXGCD

void exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0) x=1,y=0;
	else{
		exgcd(b,a%b,y,x),y-=a/b*x;
	}
}

线性时间求gcd矩阵

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(!Gcd[i][j]){//i和j互质
            for(int k=1;i*k<=n&&j*k<=m;k++)
                Gcd[i*k][j*k]=k;
        }
    }
}

筛法

线性素数筛

const int maxn=1e8+5;
const int maxp=5e6+5;
bool isPrime[maxn];
int Prime[maxp], primecnt = 0;
void GetPrime(int n){//筛到n
	memset(isPrime, 1, sizeof(isPrime));
	isPrime[1] = 0;//1不是素数
	for(int i = 2; i <= n; i++){
		if(isPrime[i])//没筛掉
			Prime[++primecnt] = i; //i成为下一个素数
		for(int j = 1; j <= primecnt && i*Prime[j] <= n; j++) {
			isPrime[i*Prime[j]] = 0;
			if(i % Prime[j] == 0)//i中也含有Prime[j]这个因子
				break;
		}
	}
}

线性筛欧拉函数&莫比乌斯函数

const int maxn=5e6+5;
bool isPrime[maxn];
int Prime[maxn], primecnt = 0;
ll phi[maxn],mu[maxn];
void getPrime(int n){
	memset(isPrime, 1, sizeof(isPrime));
	isPrime[1] = 0;
	phi[1] = mu[1] = 1;
	for(int i = 2; i <= n; i++){
		if(isPrime[i]){
			Prime[++primecnt] = i;
			phi[i]=i-1;
			mu[i]=-1;
		}
		for(int j = 1; j <= primecnt && i*Prime[j] <= n; j++) {
			isPrime[i*Prime[j]] = 0;
			if(i % Prime[j] == 0){
                phi[i*Prime[j]]=phi[i]*Prime[j];
                mu[i*Prime[j]]=0;
				break;
			}
			else{
                phi[i*Prime[j]]=phi[i]*(Prime[j]-1);
                mu[i*Prime[j]]=-1*mu[i];
			}
		}
	}
}

质因数分解

质因数分解_预处理法

GetPrime(maxn-5);
int temp=n;
int num=0;
for(int i=1;i<=primecnt;i++){
    while(temp%Prime[i]==0){
        temp/=Prime[i];
        num++;
    }
    if(temp<Prime[i]*Prime[i]){
        break;
    }
}
if(temp>1){
    num++;
}

质因数分解_O(sqrt(n))

int temp=n;
int srt=sqrt(n);
int num=0;
for(int i=2;i<=srt;i++){
    while(temp%i==0){
        temp/=i;
        num++;
    }
}
if(temp>1){
    num++;
}

取模相关

快速乘

inline ll fm(ll x,ll y,ll mod){
    ll ans=0;
    while(y>0){
        if(y&1)ans=(ans+x)%mod;
        y>>=1;
        x=(x+x)%mod;
    }
    return ans;
}

快速幂

inline ll fp(ll b,ll p,ll mod){
    ll ans=1;
    while(p){
        if(p&1)ans=fm(ans,b,mod);
        p>>=1;
//        b=fm(b,b,mod);
        b=b*b%mod;
    }
    return ans;
}

线性时间递推1-n逆元

//要求p为质数
inv[1]=1;
for(int i=2;i<=n;i++){
    inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}

递归求逆元

//要求mod为质数,比快速幂要快
ll inv(ll a) {
    if(a == 1)return 1;
    return inv(mod%a)*(mod-mod/a)%mod;
}

扩展欧几里得求逆元

void exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0) x=1,y=0;
	else{
		exgcd(b,a%b,y,x),y-=a/b*x;
	}
}
ll inv(ll a){//要求a和mod互质
    if(__gcd(a,mod)!=1){
        return -1;
    }
    else{
        ll x,y;
        exgcd(a,mod,x,y);
        x=(x%mod+mod)%mod;
        return x;
    }
}

组合数

常用公式

• (C_n^m=C_{n-1}^{m-1}+C_{n-1}^m)
• (sum_{n=0}^{r}C_n^k=C_{r+1}^{k+1})
• 杨辉三角第i行j列(从0开始)的值为(C_{i+j}^i)

线性递推求组合数

对于C(n,m)如果n<mod可以用预处理阶乘逆元求解，但是n(ge)mod时后面的阶乘和mod不是互质的，就没有逆元了，倒退前面的逆元也会出错（全部为0）

//O(n)预处理阶乘逆元,O(1)求解，要求n<mod且mod为质数
void init(int n){
    fac[0]=1;
    for(int i=1;i<=n;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    finv[n]=fp(fac[n],mod-2);
    for(int i=n-1;i>=0;i--){
        finv[i]=finv[i+1]*(i+1)%mod;
    }
}
ll C(ll n,ll m){
    if(m<0 || m>n) return 0;
    return fac[n]*finv[n-m]%mod*finv[m]%mod;
}

Lucas定理求组合数

如果组合数的n可能大于mod，用阶乘逆元的方法就不成立，因为后面的阶乘和mod不互质不存在逆元。因此要用lucas定理转换为n小于mod的情况求解。

【Lucas定理】 Lucas(n,m,p)=C(n%p,m%p)*Lucas(n/p,m/p,p)

• 要求p为质数

ll C(ll n,ll m){//要求n<mod
    if(m<0 || m>n) return 0;
    else return fac[n]*fp(fac[n-m],mod-2)%mod*fp(fac[m],mod-2)%mod;
}
ll Lucas(ll n,ll m){//要求mod为质数
    if(!m) return 1;
    else return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}

二次剩余

/*洛谷P5491
若有解，则按模p后递增的顺序输出在模p意义下的全部解.
若两解相同，只输出其中一个,
若无解，则输出Hola!
*/
#include <cstdio>
#include <cstdlib>
typedef long long ll;

int mod;
ll I_mul_I; // 虚数单位的平方

struct complex {
    ll real, imag;
    complex(ll real = 0, ll imag = 0): real(real), imag(imag) { }
};
inline bool operator == (complex x, complex y) {
    return x.real == y.real and x.imag == y.imag;
}
inline complex operator * (complex x, complex y) {
    return complex((x.real * y.real + I_mul_I * x.imag % mod * y.imag) % mod,
            (x.imag * y.real + x.real * y.imag) % mod);
}

complex power(complex x, int k) {
    complex res = 1;
    while(k) {
        if(k & 1) res = res * x;
        x = x * x;
        k >>= 1;
    }
    return res;
}

bool check_if_residue(int x) {//判断x是否是模p意义下的二次剩余
    return power(x, (mod - 1) >> 1) == 1;
}

void solve(int n, int p, int &x0, int &x1) {
    mod = p;

    ll a = rand() % mod;
    while(!a or check_if_residue((a * a + mod - n) % mod))
        a = rand() % mod;
    I_mul_I = (a * a + mod - n) % mod;

    x0 = int(power(complex(a, 1), (mod + 1) >> 1).real);
    x1 = mod - x0;
}
int main (){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,p,x0,x1;
        scanf("%d%d",&n,&p);
        mod = p;
        if(n==0){//若n为0，有一个解0
            printf("0
");
        }
        else if(check_if_residue(n)){//n不为0且有解，则必有一对不同解
            solve(n,p,x0,x1);
            if(x0<x1){
                printf("%d %d
",x0,x1);
            }
            else{
                printf("%d %d
",x1,x0);
            }
        }
        else{
            printf("Hola!
");
        }
    }
}

中国剩余定理