0.整数取余

1.加-减-乘

定理：整数的加、减、乘对于取余的右分配律.

注意，在计算减法时，通常需要加 c ，防止变成负数.

计算乘法时，如果 c 较大（<=64位整数范围）。
1.可以使用快速乘进行计算，与快速幂类似，复杂度为

, a=1e17, b=1e17, c=1e18。
2.用__int128 类型

ll FastMul(ll a, ll b, ll p)
{
    a %= p;
    ll ans = 0;
    while (b > 0)
    {
        if (b & 1) ans = (ans + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return ans;
}

typedef __int128 IN;
// 16字节 2^128（sizeof()）
// 2^128 39位 340282366920938463463374607431768211456

void scan(IN &x)//输入
{
    x = 0; int f = 1; char ch = getchar(); 
    while(!isdigit(ch)) f ^= (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = x*10 + ch-'0',ch = getchar();
    x = f ? x : -x;
}
void Print(IN x)
{
        if (x < 0) x = -x, putchar('-');
    if (x > 9) Print(x/10);
    putchar(x%10 + '0');
}

2.快速幂

求 a ^ b。 如何快速求呢？ 很显然：

所以求a^b 先求 a^(b/2)。同理求a^(b/2) 先求a^(b/4)。这样的递归听起来很合适。怎么写成循环呢：举个栗子：a^15 15=1111(就是除以2四次的余数) = 2^3 + 2^2 + 2^1 + 2^0.所以a^15 = a^(2^3) * a^(2^2) * a^(2^1) * a^(2^0)。所以b&1，说明要乘一个a^(k)。

ll Ksm(ll a, ll b, ll mod)// Fpow
{
    a %= mod;
    ll res = 1;
    while (b)
    {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

越狱-排列

n个人 每个人可以有m种信仰 总m^n 第一个人选定了， 第二个就只有m-1种， 第三个可以和第一个一样--也是m-1种(m-1^(n-1)) 。所以不越狱的数量就是 m*(m-1^(n-1))。

3.除法取余

如何计算

？有时可以找一个乘法逆元

，那么就有

.

费马小定理

如果c是素数：（乘法逆元原理）

ll Inv(ll b, ll p)
{
        return Ksm(b, p-2);
}

a=b*k，则我们称之为b整除a，记作b|a. 若b|a:

。即: a是整数，p是质数，a-p互质(即两者只有公约数1)，那么a^(p-1) % p = 1。 当遇到数论除法时，不应该是直接除以这个数，而是应该乘以它的乘法逆元。逆元的计算可以用拓展gcd。比如 x=1/n (mod N)，即 x*n=1(mod N)。由于我们做题时N常常为1e9+7，而1e9+7是个素数，所以满足了费马小定理，而满足费马小定理说明解唯一，所以直接得出x=n^(N-2), x 即为1/n关于模N的乘法逆元。

4.杂-判平方数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1000;

bool Issq0(ll num)//log(n)
{
    ll lt = 0, rt = num, md;
    while (lt <= rt)
    {
        md = lt+rt >> 1;
        if (md * md == num)     return true;
        else if (md * md < num) lt = md+1;
        else rt = md - 1;
    }
    return false;
}

bool Issq1(ll num)// 根号(n) 
{// 从0开始时考虑   0和1 
    for (ll i = 0; i * i <= num; ++i)
        if (i * i == num) return true;
    return false;
}

int main()
{
    for (ll i = 0; i < M; ++i)
    {
        if (Issq0(i)) printf("%lld ", i);
        if (Issq1(i)) printf(" %lld\n", i);
    }
    return 0;
}