小知识点

数论

求小于等于N的与N互质的数的和：ans=N*phi(N)/2

最大公约数公式：

int gcd(int a,int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
我们可以知道的
1.gcd(0,b)=b;
2.gcd(a,b)=gcd(b,a%b);

最小公倍数：

int lcm=a/gcd(a,b)*b；(防止爆longlong)

给了两个互质的数A，B。
A*x+B*y（x>=0,y>=0)
问最大不能表示的数，和不能表示的数的个数。

数论知识；
个数就是（A-1）*（B-1）/2;
最大不能表示的数就是 A*B-A-B;

要求解的是N阶乘的结果有多少个0？(1<=N<=1000000000)
注意一下几个方面：
1、任何一个自然数都可分解质因数。N！=1*2*3*（2*2）*5*（2*3）*...*N=2^a*3^b*5^c*7^d......=（2*5）^c*2^(a-c)*3^b*7^d......=10^c*2^(a-c)*3^b*7^d......
2、两数相乘产生0，是因为2和5相乘。又由于在分解质因数时小的质数的幂次一定>=大的质数的幂次，在N!中2的个数显然大于5的个数，故解决该题转化成找出N！中5的幂次。
3、如何找出5的幂次呢?其实就是 N!中：是5的倍数的数+是5^2的倍数的数+5^3的倍数的数+.....
如50!中： 
含有10个5的倍数的数：5,15,20,25,30,35,40,45,50 [50/5=10] 
含有2个5^2的倍数的数：25,50 [50/(5^2)=2] 
可见N!中一共有12个5相乘，那么N!结果中的0也必有12个。

如何求素数

void pri()
{
    int num=0,i,j,k;
    for(i=1;i<=20000;i++)
    {
        k=(int)sqrt(i);
        for(j=2;j<=k;j++)
            if(i%j==0)
              break;
        if(j>k)
            a[num++]=i;
    }
    /*for(i=0;i<num;i++)
        printf("%d ",a[i]);*/
}

素数筛选模板

O（n）
#define MAXN 1000010
int ans[MAXN];
bool vis[MAXN];;
void pri()//素数筛选
{
    int t=0;
    memset(vis,true,sizeof(vis));
    for(int i=2;i<=MAXN;i++)
    {
        if(vis[i]==1)
        {
            t++;
            ans[t]=i;
        }
        for(int j=1;((j<=t)&&(i*ans[j]<=MAXN));j++)
        {
            vis[i*ans[j]]=false;
            if(i%ans[j]==0)
                break;
        }
    }
}
O(nlog(n)):
const int maxn=100000+10;
bool v[maxn];
int ans[maxn];
void getPrime(int n,int &tot)
{
    tot=0;
    for(int i=2;i<=n;i++)
        v[i]=true;
    for(int i=2;i<n;i++)
        if(v[i])
        {
            if(n/i<i) break;
            for(int j=i*i;j<=n;j+=i)
                v[j]=false;
        }
    for(int i=2;i<=n;++i)
        if(v[i])ans[++tot]=i;
}

欧拉函数

//phi(n)为不超过n且与n互质的正整数个数
int phi(int n)
{
    int m=(int)sqrt(n+0.5);
    int ans=n;
    for(int i=2;i<=m;i++)
        if(n%i==0)
    {    
        ans=ans/i*(i-1);
        while(n%i==0)
            n/=i;
    }
    if(n>1)
        ans=ans/n*(n-1);
    return ans;
}

扩展欧几里得

求方程 ax + by = gcd(a,b)的一组解，这组解x为最小的正整数。
通解为$x = x + k*b/gcd(a,b)$ , $y = y - k*a/gcd(a,b)$

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

费马小定理

p是素数 gcd(a,p)=1;
a^(p-1) %p = 1

欧拉定理

gcd(a,p)=1;

同余式：a=b(%m)表示a%m=b%m或者a+km=b;
同余方程：ax=b(%m),求解x相当于解ax+my=b;

中国剩余定理

求模线性方程组$x \mod m_i = a_i$的最小正整数解。

    #include<bits/stdc++.h>
    typedef long long LL;
    using namespace std;
    LL exgcd(LL a, LL b, LL &x, LL &y)
    {
        if (b == 0)
        {
            x = 1;
            y = 0;
            return a;
        }
        LL ret = exgcd(b, a % b, x, y);
        LL t = x;
        x = y;
        y = t - (a / b) * y;
        return ret;
    }
    LL lcm(LL a, LL b)
    {
        return a / __gcd(a, b) * b;
    }
    LL CRT(LL m[], LL a[], int n)
    {
        LL X = a[1];
        LL LCM = m[1];
        for (int i = 2; i <= n; i++)
        {
            LL x, y;
            a[i] -= X;
            a[i] = (a[i] % m[i] + m[i]) % m[i];
            int d = exgcd(LCM, m[i], x, y);
            if (a[i] % d) return -1;
            x *= a[i] / d;
            x = (x % (m[i] / d) + m[i] / d) % (m[i] / d);
            X += LCM * x;
            LCM = lcm(LCM, m[i]);
        }
        return X;
    }

求小于某个数n的素数的个数 $n \leq 10^{11}$

    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll f[340000], g[340000], n;
    void init()
    {
        ll i, j, m;
        for(m = 1; m * m <= n; ++m)f[m] = n / m - 1;
        for(i = 1; i <= m; ++i)g[i] = i - 1;
        for(i = 2; i <= m; ++i)
        {
            if(g[i] == g[i - 1])continue;
            for(j = 1; j <= min(m - 1, n / i / i); ++j)
            {
                if(i * j < m)f[j] -= f[i * j] - g[i - 1];
                else f[j] -= g[n / i / j] - g[i - 1];
            }
            for(j = m; j >= i * i; --j)g[j] -= g[j / i] - g[i - 1];
        }
    }
    int main()
    {
        while(scanf("%lld", &n) != EOF)
        {
            init();
            cout << f[1] << endl;
        }
        return 0;
    }

线性预处理逆元

注意inv的数据类型为long long，否则会爆int

for (int i = 2; i < MAXN; i++) inv[i]  = (MOD - MOD / i) * inv[MOD % i] % MOD;