数论之 素因子分解,素数筛选法,欧拉函数和扩展欧几里得算法 (整理)

简介:
今天突然想复习一下数论,也就顺便整理了一下关于数论的基础知识,
以后用的时候直接用就行了,也不用现敲了,其实就是有点懒。。。。

具体解释都在代码里有解释

直接上代码了:


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;

#define MM(a) memset(a,0,sizeof(a))

typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1e4+5;
const int mod = 1000000007;
const double eps = 1e-7;
bool prime[maxn];
int p[maxn],k;
///素数筛选
void isprime()
{
    k = 0;
    MM(prime);
    for(int i=2; i<maxn; i++)
    {
        if(!prime[i])
        {
            p[k++] = i;
            for(int j=i*i; j<maxn; j+=i)
                prime[j] = 1;
        }
    }
}
int fac[maxn], num[maxn], cnt;
///分解素因子算法
void Dec(int x)
{
    MM(num);
    cnt = 0;
    for(int i=0; p[i]*p[i]<=x&&i<k; i++)
    {
        if(x%p[i] == 0)
        {
            fac[cnt] = p[i];
            while(x%p[i] == 0)
            {
                num[cnt]++;
                x /= p[i];
            }
            cnt++;
        }
    }
    if(x > 1)
    {
        fac[cnt] = x;
        num[cnt++] = 1;
    }
}
///欧拉公式的延伸:一个数的所有质因子之和是euler(n)*n/2
int Euler(int m)
{
    int ret = m;
    for(int i=2; i*i<=m; i++)
    {
        if(m%i == 0)
            ret -= ret/i;
        while(m%i == 0)
            m /= i;
    }
    if(m > 1)
        ret -= ret/m;
    return ret;
}
///最大公约数
LL gcd(LL x, LL y)
{
    if(y == 0)
        return x;
    return gcd(y, x%y);
}
///扩展欧几里得算法
void exgcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a%b, x, y);
    LL tmp = x;
    x = y;
    y = tmp-(a/b)*y;
}

int main()
{
    int m, t;
    //isprime();
    cin>>t;
    while(t--)
    {
///素因子分解
        /**
        cin>>m
        Dec(m);
        for(int i=0; i<cnt-1; i++)
            for(int j=0; j<num[i]; j++)
                cout<<fac[i]<<'*';
        for(int i=0; i<num[cnt-1]-1; i++)
            cout<<fac[cnt-1]<<"*";
        cout<<fac[cnt-1]<<endl;
        **/
///欧拉函数
        /**cout<<Euler(m)<<endl;**/

///扩展欧几里得算法
        /**
        LL a, b, x, y;
        cin>>a>>b;
        if(gcd(a,b) != 1)///没有解
        {
            puts("Sorry");
            continue;
        }
        exgcd(a, b, x, y);
        x = (b + x % b) % b;
        y = (1 - a * x) / b;
        cout<< x << " " << y << endl;
        **/
    }
    return 0;
}


目录
相关文章
|
2月前
|
XML JavaScript 前端开发
学习react基础(1)_虚拟dom、diff算法、函数和class创建组件
本文介绍了React的核心概念,包括虚拟DOM、Diff算法以及如何通过函数和类创建React组件。
28 2
|
2月前
|
资源调度 算法
基于迭代扩展卡尔曼滤波算法的倒立摆控制系统matlab仿真
本课题研究基于迭代扩展卡尔曼滤波算法的倒立摆控制系统,并对比UKF、EKF、迭代UKF和迭代EKF的控制效果。倒立摆作为典型的非线性系统,适用于评估不同滤波方法的性能。UKF采用无迹变换逼近非线性函数,避免了EKF中的截断误差;EKF则通过泰勒级数展开近似非线性函数;迭代EKF和迭代UKF通过多次迭代提高状态估计精度。系统使用MATLAB 2022a进行仿真和分析,结果显示UKF和迭代UKF在非线性强的系统中表现更佳,但计算复杂度较高;EKF和迭代EKF则更适合维数较高或计算受限的场景。
|
3月前
|
算法
【Azure Developer】完成算法第4版书中,第一节基础编码中的数组函数 histogrm()
【Azure Developer】完成算法第4版书中,第一节基础编码中的数组函数 histogrm()
|
3月前
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
|
4月前
|
算法 Python
`scipy.optimize`模块提供了许多用于优化问题的函数和算法。这些算法可以用于找到函数的最小值、最大值、零点等。
`scipy.optimize`模块提供了许多用于优化问题的函数和算法。这些算法可以用于找到函数的最小值、最大值、零点等。
|
4月前
|
算法 安全 数据安全/隐私保护
支付系统---微信支付09------数字签名,现在Bob想要给Pink写一封信,信件的内容不需要加密,怎样能够保证信息的完整性,使用信息完整性的主要手段是摘要算法,散列函数,哈希函数,H称为数据指纹
支付系统---微信支付09------数字签名,现在Bob想要给Pink写一封信,信件的内容不需要加密,怎样能够保证信息的完整性,使用信息完整性的主要手段是摘要算法,散列函数,哈希函数,H称为数据指纹
|
5月前
|
算法 vr&ar
技术好文共享:遗传算法解决函数优化
技术好文共享:遗传算法解决函数优化
|
5月前
|
算法 C语言 Python
简单遗传算法优化简单一元函数(python)
简单遗传算法优化简单一元函数(python)
44 0
|
25天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
10天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。