数论知识总结（持续更新）

有错误欢迎指出。 --天王盖地虎

1.反素数(洛谷在省选打表中也有这样的题)

1.反素数的定义:
   对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。现在给定一个数N，你能求出不超过N的最大的反质数么？
   题目链接: bzoj素数ant

#include<bits/stdc++.h>
using namespace std; const int maxn = 1e3+10;
typedef long long ll; bool vis[maxn];
int prim[maxn],cnt; ll n,ans;
void ai(){
    for(int i=2;i<maxn;i++){
        if(!vis[i]){
            prim[++cnt]=i;
            for(int j=2*i;j<maxn;j+=i){
                vis[j]=1;
            }
        }
    }
}
ll cc=-1;
void dfs(int k,ll now,ll tcnt){  //给一个数搜一下
    if(k>12){
        if(tcnt==cc){
            ans=min(ans,now);
        }
        else if(tcnt>cc){
            ans=now;
            cc=tcnt;
        }return;
    }
    ll base=prim[k];
    ll tmp=now;
    for(int i=0;tmp<=n;i++){
        dfs(k+1,tmp,tcnt*(i+1));
        tmp*=base;
    }return;
}
int main(){
    ai();
    cin>>n;
    dfs(1,1,1);
    cout<<ans<<endl;
    return 0;
}

由此可见：算数基本定理（唯一分解定理在数论中有着很大的应用），找到了某个数的质因子组成，那么它的约数个数随之确定（(a1+1)*(a2+1)…(an+1)，ai是第i个质因子的个数）。给你两个数的质因子分解情况，那么这两个数的最大公因数就是对应质因子的个数取min，最小公倍数就是取max。

2.快速乘（针对两数相乘取模之前溢出的情况，如1e14*1e14%1e15）

ll mul(ll x,ll y){
	ll res=1;
	while(y){
		if(y&1) res=res*x%mod;
		y>>1;x=x*x%mod;
	}
}

3.扩展欧几里得

    解决ax+by=c的问题，但是存在a,b,c是负数的情况，
所以输入后判断a是否为负数,如果是对a,c取反（这点不是很理解）eg.青蛙的约会那道题。

4.关于求组合数的总结

    能用数组开下的，用杨辉三角预处理，o(1)直接出结果，而且不用担心取模的问题。如果是模数是大质数的，可以用公式n!/(m!*(n-m)!)然后求个逆元即可，也可以卢卡斯，如果数组开不下，模数也不一定是大质数，可用扩展卢卡斯定理。

5.关于__int128那点事

    首先windows上的编译器不支持这个东西，编译不过但是可以先编译调试下别的错误，在洛谷oj可以在线idle调试一下，某些oj也有自测功能可以试试。不过有人说在Linux上可以运行，大家有条件可以用Ubuntu什么的试一下。

__128主要解决那些正好爆Longlong但是又不需要用到高精度的那种题，比如中国剩余定理就时常会卡这个东西，当然用Java高精度也不错，__int128熟练了效果更佳。

上板子(__int128可以跟int，long long什么的)：

#include<bits/stdc++.h>
using namespace std;
__int128 sc(){
    __int128 res=0;
    int f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') f=-1; ch=getchar();
    }
    while(isdigit(ch)){
        res=res*10+ch-'0';
        ch=getchar();
    }return res*f;
}
void print(__int128 x){
    if(x<0){
        putchar('-'); x=-x;
    }
    if(x>9){
        print(x/10);
    }
    putchar(x%10+'0');
}
int main(){
    __int128 a,b;
    a=sc();
    b=sc();
    print(a+b);
    return 0;
}