分类: 数论

  • 数论分块的证明

    $$
    \text{对于}i\text{,证明}\lfloor \frac{n}{k} \rfloor =\lfloor \frac{n}{x} \rfloor \text{,其中}x\in \left[ i,\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor \right] \lfloor \frac{n}{i} \rfloor =\frac{n}{x}-c\left( 0\le c<1 \right) 
    \\
    0\le c=\frac{n}{x}-\lfloor \frac{n}{i} \rfloor <1
    \\
    \frac{n}{x}\ge \lfloor \frac{n}{i} \rfloor n\ge x\lfloor \frac{n}{i} \rfloor 
    \\
    i\le x\le \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor 
    $$

     

  • 一点关于扩展欧几里得算法的理解

    由于一直无法理解扩展欧几里得算法以及背不下代码,于是花了半节生物课推了一个可以使用普通gcd快速幂代替扩展欧几里得算法的东西….qwq

    扩展欧几里得算法解的是方程$ax+by=c$,我们先把方程做一些处理,设$d=gcd(a,b)$,如果$c\ mod\ d \neq 0$,则原方程无整数解,否则方程两边同时除以$d$得到新方程$ex+fy=g$。

    将该方程放到膜$f$意义下可得$ex=g(mod\ f)$,然后因为$e$与$g$互质,所以方程两边同时乘$e^{-1}$(可以通过快速幂求出)可得$x=e^{-1}g(mod\ f)$,于是解出$x$,将$x$代入原方程即可解出$y$。

     

  • SDOI2015 约数个数和

    手推出来的为数不多的几道数学题,突然很想写一篇博客..

    http://lifecraft-mc.com:81/problem/1026

    题意:设d(ij)表示ij的约数个数,求

    #\sum _{i=1}^N \sum _{j=1}^M d(ij)#

    ,$N,M\leq 50000$ 50000组数据

    首先,$d(ij)=\sum _{x|i}\sum _{y|j}[gcd(x,y)==1]$(其中[gcd(x,y)==1]表示gcd(x,y)=1时,值为1,否则为0)

    一个很好的处理[xxx]的方法:$[x==1]=\sum _{i|x}\mu(i)$

    然后可得#\sum _{i=1}^N\sum _{j=1}^M\sum _{x|i}\sum _{y|j} [gcd(x,y)==1]=\sum _{i=1}^N\sum _{j=1}^M\sum _{x|i}\sum _{y|j}\sum  _{k|gcd(x,y)}\mu(k)#

    有一个结论,一个数n的约数的集合中每个数除以k所得的集合等于n/k约数的集合,所以枚举k可以得到

    #\sum _{k=1}^N\sum _{i=1}^{\frac N k}\sum _{j=1}^{\frac M k}\sum _{x|i}\sum _{y|j}\mu(k)#

    原先我们根据i j来枚举x y 现在我们根据x y来枚举i j

    #\sum _{k=1}^N \mu(k) \sum _{x=1}^{\frac N k} \sum _{y=1}^{\frac M k} \sum _{x|i}\sum _{y|j} = \sum _{k=1}^N \mu(k) \sum _{x=1}^{\frac N k} \sum _{y=1}^{\frac M k} \frac N {kx} \frac M {ky}#

    继续

    #\sum _{k=1}^N\mu(k)\sum _{x=1}^{\frac N k}\frac N{kx}\sum _{y=1}^{\frac M k}\frac M{ky}#

    可以发现最后两个求和符号有相似的外形,所以我们可以把他们统一起来,设

    #f(n)=\sum _{x=1}^N  \frac N x#

    原式可变形为

    #\sum _{k=1}^N \mu(k)f(\frac N k)f(\frac M k)#

    这样的话可以预处理出所有的f(n),每组询问就可以在sqrt(N)的时间内处理.

  • 快速幂与矩阵快速幂

    首先介绍快速幂:

    快速幂可以在常数时间内计算$$a^b$$,而朴素的算法则需要$$O(b)$$

    思想:将b转换为二进制,则

    $$b=1+2+4+8+……$$

    $$a^b=a^{1}*a^{2}*a^{4}*….=a^{1}*(a^{1})^{2}*((a^{1})^{2})^{2}*…$$

    例如:

    求$$3^5$$

    $$\because 5=1+4$$

    $$\therefore 3^5=3^{1+4}=3^1*3^4$$

    先计算$$3^1=3$$,结果乘上3 然后计算$$(3^1)^2=3^2=9$$,然后计算$$(3^2)^2=3^4=81$$,结果乘上81,最终结果为$$3*81=243$$

    代码:

     

    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    using namespace std;
    using int_t = long long int;
    
    int_t fastPower(int_t base, int_t index) {
        //结果
        int_t result = 1;
        //只要指数不为0就一直循环
        while (index) {
            //index的最低位为1,结果中应该乘上base的对应次幂
            if (index & 1) {
                result = result*base;
            }
            base = base*base;
            //index右移一位
            index >>= 1;
        }
        return result;
    }
    
    int main() {
        int_t base, index;
        while (true) {
            cin >> base>>index;
            if (base == 0 && index == 0) break;
            cout << fastPower(base, index) << endl;
    
        }
        return 0;
    }
    

    矩阵快速幂:

    使用快速幂的思想来计算矩阵的幂

     

    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    using namespace std;
    using int_t = unsigned long long int;
    const int_t mod = (int_t) 1e9 + 7;
    //Matrix的前置声明,用于下面两个函数
    template 
    class Matrix;
    //友元函数的声明
    //模板类的友元函数必须显式的写明模板
    template 
    ostream& operator<<(ostream & os, const Matrix & mat);
    template 
    istream& operator>>(istream & os, const Matrix & mat);
    
    template 
    class Matrix {
    private:
        ValType* data;
        int_t row;
        int_t col;
        int_t size;
        int_t num;
    public:
        //析构函数,释放内存
        ~Matrix() {
            delete[] data;
        }
        //拷贝构造函数
        Matrix(const Matrix& other) :
        row(other.row), col(other.col), size(other.size), num(other.num) {
            data = new ValType[other.num];
            memcpy(data, other.data, other.size);
        }
        //默认构造函数,动态分配内存
        Matrix(int_t r, int_t c) :
        row(r), col(c) {
            this->row = r;
            this->col = c;
            num = (row + 1)*(col + 1);
            data = new ValType[num];
            size = sizeof (ValType) * num;
            memset(data, 0, size);
        }
        //访问矩阵的某个元素
        ValType& at(int_t r, int_t c) {
            return data[c + r * col];
        }
        //重载的*运算符,矩阵无法相乘时会抛出异常
        Matrix operator*(Matrix& mat) throw (const char*) {
            if (this->col != mat.row) throw "Column number of matrix1 doesn't equals that in matrix2";
            Matrix result(this->row, mat.col);
            for (int_t i = 1; i <= this->row; i++) {
                for (int_t j = 1; j <= mat.col; j++) {
                    int_t sum = 0;
                    for (int_t x = 1; x <= this->col; x++) {
                        sum = (sum % mod + at(i, x) % mod * mat.at(x, j) % mod) % mod;
                    }
                    result.at(i, j) += sum % mod;
                }
            }
            return result;
        }
    
        int_t getCol() const {
            return col;
        }
    
        int_t getRow() const {
            return row;
        }
        //赋值构造函数
        Matrix & operator=(const Matrix & other) {
            this->col = other.col;
            this->num = other.num;
            this->row = other.row;
            this->size = other.size;
            this->data = new ValType[num];
            memcpy(data, other.data, size);
        }
        //友元,函数名后必须写<>以告诉编译器这个友元使用了模板,如果不能从参数中推断模板类型那么还必须在<>内写上模板类型
        friend ostream& operator<< <>(ostream & os, const Matrix & mat);
        friend istream& operator>> <>(istream & os, const Matrix & mat);
    };
    //友元函数的实现
    template 
    ostream & operator<<(ostream & os, Matrix & mat) {
        for (int_t i = 1; i <= mat.getRow(); i++) {
            for (int_t j = 1; j <= mat.getCol(); j++) {
                os << mat.at(i, j) % mod << " ";
            }
            os << endl;
        }
        return os;
    }
    
    template 
    istream & operator>>(istream & is, Matrix & mat) {
        for (int_t i = 1; i <= mat.getRow(); i++) {
            for (int_t j = 1; j <= mat.getCol(); j++) {
                is >> mat.at(i, j);
                mat.at(i, j) %= mod;
            }
        }
        return is;
    }
    using MatType = Matrix;
    
    int main() {
    
    
        int_t n, index;
        cin >> n>>index;
        MatType mat(n, n);
        cin>>mat;
        MatType result = mat;
        //普通的快速幂
        for (index--; index; index>>=1,mat = mat * mat) {
            if (index & 1) result = result * mat;
        }
        cout << result;
        return 0;
    }
    

    此外,矩阵$$A=\begin{bmatrix}
    0&1 \\
    1&1
    \end{bmatrix}$$的n次方所得的矩阵的对角线上的元素即为斐波那契数列的第n项。

  • 乘法逆元

    如果$$ax\equiv 1(mod n)$$则称x为a模n意义下的逆

    则有$$ax-ny=1$$,然后用扩展欧几里得算法求解即可。

  • 唯一分解定理

    任何一个正整数都可以写成几个质数的幂次方之积,即
    $$n={p_1}^{k_1} {p_2}^{k_2} {p_3}^{k_3} {p_4}^{k_4} …..{p_m}^{k_m} $$ 其中$$p_m$$为素数,$$k_m$$为非负整数

    例如

    $$30=2^1*3^1*5^1$$

    $$40=5*8=5^{1}*2^{3}$$

    $$72=2*36=2^1*6^2$$

    代码实现:

     

    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    using namespace std;
    using int_t = long long int;
    
    map func(int_t x) {
        //map
        //x=p1^k1*p2^k2...........pn^kn
        map result;
        for (int_t i = 2; i <= x; i++) {
            //如果x的可以整除i,则结果中i的指数+1
            while (x % i == 0) {
                result[i]++;
                x /= i;
            }
        }
        return result;
    }
    
    int main() {
        int_t x;
        while (cin >> x) {
            auto result = func(x);
            cout << x << " = ";
            //请手动忽略最后多余的乘号
            for (auto p : result) {
                cout << p.first << "^" << p.second << " * ";
            }
            cout << endl;
        }
    }
    
  • 欧拉函数

    设函数$$\phi (x)$$为不超过x且与x互素的正整数的个数(两个数互素,则两个数的最大公因数为1)

    则$$\phi(x)=x(1-\frac {1} {p_1})(1-\frac {1} {p_2})(1-\frac {1} {p_3})(1-\frac {1} {p_4})·····(1-\frac {1} {p_n})$$

    其中$$p_n$$为将x通过唯一分解定理所得的式子的底数,即$$n={p_1}^{k_1} {p_2}^{k_2} {p_3}^{k_3} {p_4}^{k_4} …..{p_m}^{k_m} $$ 其中$$p_n$$为素数

     

    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    using namespace std;
    using int_t = long long int;
    
    int_t func(int_t x) {
        int_t result = x;
        for (int_t i = 2; i <= x; i++) {
            //如果x的可以整除i,则结果中i的指数+1
            if (x % i == 0) {
                //    result = result * (i - 1) / i;
                //先乘后除防止溢出
                result = result / i * (i - 1);
                while (x % i == 0) x /= i;
            }
        }
        if (x > 1) result = result / x * (x - 1);
        return result;
    }
    
    int main() {
        int_t x;
        while (cin >> x) {
            int_t result = func(x);
            cout<
    

    或者可以通过类似于线性筛素数的方式求出一定范围内所有的数的欧拉函数值

    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    
    using namespace std;
    using int_t = long long int;
    const int_t MAX = 100000;
    int_t phi[MAX + 1];
    int main() {
        int_t x;
        cin>>x;
        memset(phi, 0, sizeof (phi));
        phi[1] = 1;
        for (int_t i = 2; i <= x; i++) {
            if (phi[i] == 0) {
                for (int_t j = i; j <= x; j = j + i) {
                    if (phi[j] == 0) phi[j] = j;
                    phi[j] = phi[j] / i * (i - 1);
                }
            }
    
        }
        for(int_t i=1;i<=x;i++) cout<<"phi("<<i<<") = "<<phi[i]<<endl;
    
    }
    
  • 线性筛素数

    使用欧拉筛法可以接近线性的时间内筛出一定范围内所有素数。

    基本思想:如果$$a$$是素数,那么$$a*1,a*2,a*3,a*4,a*5…..$$都不是素数,这样就可以对一定范围内的非素数进行标记。

    代码:

     

    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    using namespace std;
    using int_t = long long int;
    const int_t MAX = 10000;
    char isPrime[MAX + 1];
    vector primeTable;
    
    int main() {
        //初始时,假设所有数都是素数
        memset(isPrime, 1, sizeof (isPrime));
        int_t n;
        cin>>n;
        //1当然不是素数
        isPrime[1] = 0;
        //i只需要枚举到sqrt(n),因为i>sqrt(n)的情况已经被考虑过了
        for (int_t i = 2; i <= sqrt(n + 0.5); i++) {
            //当外层循环执行到i时,如果i仍未被标记非素数,就说明i真的是素数
            //如果i不是素数,那样就不需要继续标记i*2,i*3,i*4....了 因为这些情况已经被标记了
            if (isPrime[i]) {
                for (int_t j = i * i; j <= n; j =j+i) {
                    isPrime[j] = false;
                }
            }
        }
        for (int_t i = 1; i <= n; i++) {
            if (isPrime[i]) {
                primeTable.push_back(i);
            }
        }
        for (int_t prime : primeTable) {
            cout << prime << endl;
        }
    
        return 0;
    }
    
  • 欧几里得算法与扩展欧几里得算法

    欧几里得算法,即人教版高中数学必修三上的辗转相除法

    用于求两个整数的最大公因数(即gcd(a,b))
    注:a b的最小公倍数等于$$\frac {ab}{\gcd \left(a,b\right)}$$

    int gcd(int a, int b) {
        //边界b==0 此时a就是结果
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
    

    扩展欧几里得算法:在求最大公约数的同时求出方程$$ax+by=gcd(a,b)$$的一组整数解,使|x|+|y|最小

    //a b 方程中的a b 
    //gcd 用来存放gcd(a,b)
    //x y 用来存放解
    void exgcd(int a, int b, int & gcd, int& x, int& y) {
        //边界b==0 此时a就是结果
        if (b == 0) {
            x = 1;
            y = 0;
            gcd = a;
        } else {
            exgcd(b, a % b, gcd, y, x);
            y -= (a / b) * x;
    
        }
    }
    

    求出$$ax+by=gcd(a,b)$$的解之后,如果$$c$$可以整除$$gcd(a,b)$$ 就说明方程$$ax+by=c$$存在整数解$$x_0,y_0$$,而且这组解为$$x_1=x_0*c/gcd(a,b),y_1=y_0*c/gcd(a,b)$$

    然后,如果$$x_1,y_1$$是方程$$ax+by=c$$的解,则$$x_1+k*a/gcd(a,b),y_1-k*b/gcd(a,b)$$都是方程$$ax+by=c$$的解