首页 > 其他分享 >数论

数论

时间：2022-10-08 22:24:42浏览次数：29  
标签：prime gcd 数论 a1 int k1 m1

数学

质数，约数，欧拉函数，快速幂，扩展欧几里得算法，中国剩余定理，高斯消元，求组合数，容斥原理，博弈论等内容。

质数

质数的判定

试除法 O(sqrt(n))

bool is_prime(int x)
{
    if(x<2) return 0;
    for(int i=2;i<=x/i;i++) //sqrt(n)
        if(x%i==0) return 0;
    return 1;
}

分解质因数

试除法

对于每个x，最多包含一个大于sqr(n)的质因数，
所以只需要枚举到sqrt(n).

void divide(int x)
{
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)
        {   
            int p=0;
            while(x%i==0)
            { 
                x/=i;
                p++;//记录次数
            }
             printf("%d %d\n",i,p);  
        }
    }
    if(x>1) printf("%d %d\n",x,1);
    printf("\n");
}

质数筛

朴素(nlogn)

//筛1~n的所有质数
void get_prime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            cnt++;
            for(int j=i+i;j<=n;j+=i) st[j]=1;
        }
    }
}

埃氏筛O(nloglogn)

只筛质数的倍数

void get_prime(int x)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            cnt++;
            for(int j=i+i;j<=n;j+=i) st[j]=1;
        }
    }
}

线性筛

每个合数只会被筛掉一次且只会被最小的质数筛掉。

void get_prime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) prime[cnt++]=i;
        for(int j=0;prime[j]<=n/i;j++)
        {
            st[prime[j]*i]=1;
            if(i%prime[j]==0) break;
        }
    }
}

约数

试除法求约数

vector<int> get_divisors(int n)
{
    vector<int>res;
    for(int i=1;i<=n/i;i++)
    {
        if(n%i==0)
        {
            res.push_back(i);
            if(i!=n/i) res.push_back(n/i);
        } 
    }
    sort(res.begin(),res.end());
    return res;
}

约数的个数 O(logn)

x=p1a1+p2a2....pk^ak
num=(a1+1)*(a2+1).....(ak+1)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;


int main(){
    
    unordered_map<int,int>prime;
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        for (int i=2; i<=x/i;i++)
        {
            while (x%i==0)
            {
                x/=i;
                prime[i]++;
            }            
        }
        if (x>1)prime[x]++;
    }
    LL res=1;
    for(auto pr:prime) res=res*(pr.second+1)%mod;
    printf("%d",res);
    return 0;
}

约数之和

sum=(p10+p21+...p1a1)*(p20+...p2a2)*....(pk0+...pk^ak)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;


int main(){
    
    unordered_map<int,int>prime;
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        for (int i=2; i<=x/i;i++)
        {
            while (x%i==0)
            {
                x/=i;
                prime[i]++;
            }            
        }
        if (x>1)prime[x]++;
    }
    LL res=1;
    for(auto prime:prime)
    {
        LL t=1;
        int p=prime.first,a=prime.second;
        while(a--) t=(t*p+1)%mod;
        res=res*t%mod;
    }
    printf("%lld",res);
    return 0;
}

最大公约数

欧几里得定理:c|a,c|b--->c|ax+by

int gcd(int a,int b){return b?return(b,a%b):a;}

欧拉函数

φ(n) ：1~n中与n互质的数的个数
n=p1a1*p2a2*p3a3......pkak;

φ(n)=n(1-1/p1)(1-1/p2)*...(1-1/pk);

容斥原理

1.从1~n中去掉p1,p2,p3...pk的所有倍数。

2.加上所有p1p2,p1p3...的倍数

3.减去所有p1p2p3...的倍数

...

即得上式。

筛法求欧拉函数


1.如果i为质数那么显然phi[i]=i-1;
2.if i%prime[j]==0 prime[j]是i的最小质因数，那么其已经包含在phi[i]中了，那么phi[prime[j]*i]=phi[i]*prime[j];
3.i%prime[j]!=0 phi[prime[j]*i]=prime[j]*(1-1/prime[j])*phi[i]=phi[j]*(prime[j]+1)；
  
  
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long LL;
LL prime[N],cnt,phi[N];
bool st[N];
LL get_euler(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            prime[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;prime[j]<=n/i;j++)
        {
            st[prime[j]*i]=1;
            if(i%prime[j]==0)
            {
                phi[prime[j]*i]=phi[i]*prime[j];
                break;
            }
            else phi[prime[j]*i]=phi[i]*(prime[j]-1);
        }
    }
    LL res=0;
    for(int i=1;i<=n;i++) res+=phi[i];
    return res;    
}
int main(){
    int n;
    cin>>n;
    printf("%lld\n",get_euler(n));
    return 0;
}

欧拉定理：若a与n互质则a^φ(n)≡1(mod n)

费马定理：若a与p互质且p为质数则a^p-1≡(mod p)

快速幂(反复平方法)

求 a^k mod p

O(log k)

int qm(int a,int b,int p)
{
	int res=1;
	while(b)
	{
		if(b&1) res=res*a%p;
		b>>=1;
		a=a*a%p;
	}
	return res;
}

快速幂求逆元

乘法逆元：若b,m互质,且对于任意整数a,如果b|a,则存在一个整数,
使得a/b≡a*x(mod m)则称x为b的模m乘法逆元,记为b^-1 (mod m)

b存在逆元的充要条件是b与m互质。

由费马定理得b与m互质则

a^m-1≡1(mod m)

a*a^m-2≡1(mod m)

当模数m为质数是b^m-2即为b的乘法逆元。

扩展欧几里得

裴蜀定理：若a,b为正整数,则存在x,y使得ax+by=gcd(a,b)

扩展欧几里得即已知a,b求出一对x,y满足上式。

int exgcd(int a,int b,int &x,int &y)
{
  if(!b)
  {
    x=1,y=0;
    return a;
  }
  int x1,y1;
  int d=exgcd(b,a%b,x1,y1);
  x=y1,y=x1-a/b*y1;
  return d;
}


证明：
a*x+b*y=gcd(a,b) b=0时 a*x=gcd(a,0)
即x=1,y=0;
gcd(a,b)=gcd(b,a%b);
b*x`+(a%b)y`=gcd(b,a%b)=gcd(a,b)
b*x`+(a-a/b*b)y`=gcd(a,b);
a*y`+b(x`-a/b*y`)=gcd(a,b);
故x=y`,y=x`-a/b*y`;

求一般方程

a*x+b*y=c;
将此式转化为扩展欧几里得
设d=gcd(a,b)
a*x/c*d+b*y/c*d=d;

....

中国剩余定理

中国剩余定理说明：假设整数m1,m2, ... ,mn两两互质，则对任意的整数：a1,a2, ... ,an，方程组 有解。

设M=m1m2m3....*mk;

Mi=M/mi;

因为m两两互质，所以Mi显然与mi互质，Mi^-1为Mi模mi的乘法逆元。

x通解：x=a1M1M1-1+a2M2M2-1+...

令上式模m1,因为M1与m1互质，所以得一，而M2,M3..都包含m1所以得0，因此x=a1(mod m1);

求解一般方程（无互质前提）

等价于

x=k1*m1+a1;

x=k2*m2+a2;

所以

k1* m1+a1=k2*m2+a2;

k1m1+k2m2=a2-a1;①

利用扩展欧几里得求得

k1*m1+k2*m2=gcd(m1,m2);②

d=gcd(m1,m2);

当且仅当d|(a2-a1)时①有解。

②*(a2-a1)/d=①;

所以k1=k1`*t;

通解：

k1=k1`+k*m2/d;

k2=k2`-k*m1/d;

t=m2/d;
为了得到k1的最小正整数解

(k1%t+t)%t

将k1=k1`+km2/d带入原式x=k1m1+a1;
得到

x=(k1+k*m2/d)*m1+a1; x=k*m1*m2/d + a1+k1m1;
发现与原式有相似结构
设m0=m1m2/d,a0=a1+k1`m1;

x=k*m0+a0;

得到

m1=m1*m2/d;

a1=a1+k1`*m1;

...

综上x=(x1%m1+m1)%m1;

高斯消元

  1. 把某一行乘一个非零的数
  2. 交换某两行
  3. 把某行的若干倍加到另一行上去。

完美阶梯形---有唯一解

0=非零-------无解

0=0----------无穷多解

枚举每一列c

  1. 找到这一列绝对值最大的那一行
  2. 将该行换到最上面
  3. 将该行第一个数变成一
  4. 将下面所有行的当前c列变成0.
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;
const double eps = 1e-6;

int n;
double a[N][N];


int gauss()
{
    int c, r;// c 代表 列 col ， r 代表 行 row
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;// 先找到当前这一列，绝对值最大的一个数字所在的行号
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        if (fabs(a[t][c]) < eps) continue;// 如果当前这一列的最大数都是 0 ，那么所有数都是 0，就没必要去算了，因为它的约束方程，可能在上面几行

        for (int i = c; i < n + 1; i ++ ) swap(a[t][i], a[r][i]);//// 把当前这一行，换到最上面（不是第一行，是第 r 行）去
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];// 把当前这一行的第一个数，变成 1， 方程两边同时除以 第一个数，必须要到着算，不然第一个数直接变1，系数就被篡改，后面的数字没法算
        for (int i = r + 1; i < n; i ++ )// 把当前列下面的所有数，全部消成 0
            if (fabs(a[i][c]) > eps)// 如果非0 再操作，已经是 0就没必要操作了
                for (int j = n; j >= c; j -- )// 从后往前，当前行的每个数字，都减去对应列 * 行首非0的数字，这样就能保证第一个数字是 a[i][0] -= 1*a[i][0];
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;// 这一行的工作做完，换下一行
    }

    if (r < n)// 说明剩下方程的个数是小于 n 的，说明不是唯一解，判断是无解还是无穷多解
    {// 因为已经是阶梯型，所以 r ~ n-1 的值应该都为 0
        for (int i = r; i < n; i ++ )// 
            if (fabs(a[i][n]) > eps)// a[i][n] 代表 b_i ,即 左边=0，右边=b_i,0 != b_i, 所以无解。
                return 2;
        return 1;// 否则， 0 = 0，就是r ~ n-1的方程都是多余方程
    }
    // 唯一解 ↓，从下往上回代，得到方程的解
    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[j][n] * a[i][j];//因为只要得到解，所以只用对 b_i 进行操作，中间的值，可以不用操作，因为不用输出

    return 0;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n + 1; j ++ )
            cin >> a[i][j];

    int t = gauss();

    if (t == 0)
    {
        for (int i = 0; i < n; i ++ ) printf("%.2lf\n", a[i][n]);
    }
    else if (t == 1) puts("Infinite group solutions");
    else puts("No solution");

    return 0;
}

组合数

递推式

等式左边表示从 m个元素中选取 n 个元素，而等式右边表示这一个过程的另一种实现方法：任意选择m中的某个备选元素为特殊元素，从 m 中选 n 个元素可以由此特殊元素的被包含与否分成两类情况，即 n 个被选择元素包含了特殊元素和 n 个被选择元素不包含该特殊元素。前者相当于从 m-1 个元素中选出 n-1 个元素的组合，即 ；后者相当于从 m-1 个元素中选出 n 个元素的组合，即 。

相关运用： 的二项式定理的系数，即为此数列；任何集合的子集个数也为用为此数列，而得出为 个。

卢卡斯定理

卡特兰数

....

容斥原理

在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。


简单来讲，奇加偶减

...

不妨设元素x在k个集合（ 1 ≤ k ≤ n 1 \le k \le n 1≤k≤n）中出现过，根据公式则其被计算的次数为：

根据二项式定理，可知：

标签：prime,gcd,数论,a1,int,k1,m1
From： https://www.cnblogs.com/mrkou/p/16770478.html

相关文章

  • 算法学习笔记（数学）：数论分块 + 容斥原理 + 莫比乌斯函数
    算法学习笔记（数学）：数论分块+容斥原理+莫比乌斯函数这篇文章主要是要讲一道题目（链接在这里)以及梳理一下数论分块，莫比乌斯函数，容斥原理这些知识。先介绍下知识点吧qwq......
  • 做题记录整理数论1 P6102 [EER2]谔运算（2022/10/3）
    P6102[EER2]谔运算位运算题，但是就算进数论里面吧之前说dp是我学得最烂的（其实都没好到哪里去），现在发现原来数论才是。。。由于是看题解的，而且数论题看题解和白嫖也差不多......
  • 洛谷 CF550C Divisibility by Eight（DP/数论）
    遇事不决，小学数学。https://www.luogu.com.cn/problem/CF550C题目大意：给你一个位数不超过100的非负整数N（不含前导0）。你的任务是判断这个数字能否通过去掉其中......
  • ABC 246 D - 2-variable Function（数论/暴力）
    https://atcoder.jp/contests/abc246/tasks/abc246_d题目大意：给定一个数字N，让我们求出X，这个X要满足X>=N，并且X内部可以有一对（a，b）满足a^3+a^2*b+b^2*a+b^3。找出最......
  • 数学数论全集
    扩展欧几里得定理\[ax+by=(a,b);bx_0+(a\bmodb)y_0=(a,b);x=y_0;y=(a/b)y_0+b(x_0)\]证：\({a}x+{b}y=(a,b)=(b,a\bmodb)=bx+(a\bmodb)y=bx_0+(a-(a/b)b)y......
  • 个人数论专题总结
    中国剩余定理（CRT）证明与应用问题定义给定一组同余方程：\[(S):\begin{cases}x≡a_1(\text{mod}m_1)\\x≡a_2(\text{mod}m_2)\\……\\x≡a_n(\text{mod}m_n)\\\end{cases......
  • 数论笔记
    倍数若\(a,b,k\in\mathbbN\)，且\(a\timesk=b\)，那么\(b\)是\(a\)的倍数，称\(a\)整除\(b\)，记作\(a\midb\)。\([1,n]\)中\(x\)的倍数有\(\left\lfl......
  • 2022高联P2数论
    P2:设整数\(n(n>1)\)恰有k个互不相同的质因子，记n的所有正约数之和为\(\sigma(n)\).求证：\(\sigma(n)|(2n-k)!\).既然已给出了质因子个数和\(\sigma(n)\)，那么就可设出\(n\)......
  • *ABC 245 D - Polynomial division（数论/思维）
    https://atcoder.jp/contests/abc245/tasks/abc245_d题目大意：n个数字，代表A(X)=a[0]*X^0+a[1]*X^1+......+a[n]*X^n;m个数字，代表B(X)=b[0]*X^0+b[1]*X^1+...........
  • 数论:同余，逆元，求同余方程，翡蜀定理
    同余表示两个数模上另一个数相同；写作ax=b(modp)，我们把ax=1(MODP) x称为a在p的逆元；求逆元就是求同余方程求同余方程使用扩展欧几里得法1intexgcd(inta,intb,......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99