精华内容
下载资源
问答
  • 这里讲一下算法中常用到的唯一因子分解定理: 合数a仅能以一种方式写成如下乘积形式: a = p1^e1*p2^e2*...*pr^er 其中pi为素数,p1<p2<...<pr,且ei为正整数。例如数6000=2^4*3*5^3。 证明就不讲了,...

    这里讲一下算法中常用到的唯一因子分解定理:

    合数a仅能以一种方式写成如下乘积形式:

        a = p1^e1*p2^e2*...*pr^er
        其中pi为素数,p1<p2<...<pr,且ei为正整数。例如数6000=2^4*3*5^3。

    证明就不讲了,网上一抓一大把,这里应用这个定理写了一个类,可以在分解合数的时候增加效率。

    #include <iostream>
    #include <vector>
    #include <cstring>
    
    using namespace std;
    
    #define maxn 65535
    
    class Resolve
    {
    public:
        bool list[maxn];
        vector<long long> v;
        Resolve()
        {
            find_Prime();
        }
        void find_Prime()
        {
            memset(list,true,sizeof(list));
            for(long long i=2;i<=maxn;i++)
            {
                for(long long j=i*i;j<=maxn;j+=i)
                {
                    list[j]=false;
                }
            }
            for(long long i=2;i<=maxn;i++)
            {
                if(list[i])
                    v.push_back(i);
            }
        }
        vector<long long> reso(long long x)
        {
            vector<long long>ans;
            long long k=0;
            while(x>1)
            {
                if(x%v[k]==0)
                {
                    ans.push_back(v[k]);
                    x/=v[k];
                    continue;
                }
                k++;
            }
            return ans;
        }
        ~Resolve()
        {
            vector<long long>().swap(v);
            delete[] list;
        }
    };

    最后再附上释放向量vector内存的方法。

    //方法一
    vector<int>v;
    //释放语句
    vector<int>().swap(v);
    
    //方法二,动态创建对象时
    vector<int> *v=new vector<int>();
    //释放语句
    delete[] v;

     

    展开全文
  • 高斯整数与唯一因子分解 稍微偏了点理论,数域的扩展,这里不详细记录了 主要是: 高斯整数的唯一分解 高斯整数带余除法 高斯整数公因数性质 高斯素数整除性质 勒让德两平方数之和定理 D1−D3D1−D3D_1-D_3差...

    高斯整数与唯一因子分解

    稍微偏了点理论,数域的扩展,这里不详细记录了

    主要是:

    • 高斯整数的唯一分解
    • 高斯整数带余除法
    • 高斯整数公因数性质
    • 高斯素数整除性质
    • 勒让德两平方数之和定理
    • D1D3 D 1 − D 3 差定理
    展开全文
  • 那时候,我们不会是思考为什么这种分解是存在的,更不会思考为什么这种分解唯一的。我们把老师和课本当成是权威,所说所写都是真理。稍微肯思考的孩子,动手写了几个例子,发现也确实是对的。那时候,一切只需要...

    算术基本定理

    打小学起,我们就知道正整数有一些基本单元叫做素数,它们除了1和自身外没有其他的因子。除了1之外的数,如果不是素数,就叫做合数,合数可以分解成素数的乘积,比如, 12 = 2 × 2 × 3 12=2\times 2\times 3 12=2×2×3。而且,这种分解是唯一确定的。那时候,我们不会思考为什么这种分解是存在的,更不会思考为什么这种分解是唯一的。我们把老师和课本当成是权威,所说所写都是真理。稍微勤快点的孩子,动手写了几个例子,发现也确实是对的。那时候,一切只需要陈述和应用,证明看起来是那么高不可攀。

    现在我们来看看怎么证明吧。给一个大于1的正整数,如果不是素数,就可以分解成两个更小的数的乘积,如果这两个数也不是素数,就又可以分解成比自身更小的数的乘积。这个过程是不会无限进行下去的,我们不会一直都能取到更小的数(这个是由于自然数的良序性)。于是到了有限步之后,最初给的数就写成了有限个素数的乘积。

    到目前为止,我们还不需要减法和负数。但是到了唯一性证明的时候,引入减法和负数就是必要的了。(这个并不绝对,但是会使证明更加简洁。不引入减法和负数,使用数学归纳法也是可以解决这个问题的。)首先,我们断言:一个素数 p p p如果整数两个正数的乘积 a b ab ab,那么它必定整除其中某个正数。这个依赖于带余除法。假设 p ∤ a , b p\nmid a,b pa,b,则存在 u , v , s , t ∈ Z u,v,s,t\in \mathbb{Z} u,v,s,tZ,使得 u p + v a = 1 up+va=1 up+va=1 s p + t b = 1 sp+tb=1 sp+tb=1,两式相乘得到
    ( u s p + u t b + v s a ) p + v t a b = 1 (usp+utb+vsa)p+vtab=1 (usp+utb+vsa)p+vtab=1

    从而 p ∤ a b p\nmid ab pab。这样就证明了断言。引入逆运算,对系统进行自然的扩充,会使论证过程变得更加自然。 根据这个断言,如果有两个分解式 c = p 1 p 2 ⋯ p m = q 1 q 2 ⋯ q n c=p_1p_2\cdots p_m=q_1q_2\cdots q_n c=p1p2pm=q1q2qn,则必有 p 1 ∣ q n ( 1 ) p_1|q_{n(1)} p1qn(1),因为 q n ( 1 ) q_{n(1)} qn(1)也是素数,所以就得到 p 1 = q n ( 1 ) p_1=q_{n(1)} p1=qn(1),再用消去律(整数环是整环),就可以归纳下去完成证明。

    上面这部分实际上说明了:整数环 Z \mathbb{Z} Z是唯一因子分解整环。

    完全类似地,可以说明域上的多项式环 k [ x ] k[x] k[x]也是唯一因子分解整环。

    整系数多项式

    其实整系数多项式环 Z [ x ] \mathbb{Z}[x] Z[x]也是唯一因子分解整环。它没有带余除法,但是它距离带余除法仅仅只有一步之遥——考虑有理数域上的多项式环 Q [ x ] \mathbb{Q}[x] Q[x]。毕竟除法可以做就意味着首项可以消。

    给一个整系数多项式 f f f,如果看成是有理系数多项式,就可以分解为一些 Q [ x ] \mathbb{Q}[x] Q[x]上的不可约多项式的乘积 f = f 1 ⋯ f n f=f_1\cdots f_n f=f1fn。下面考虑怎么回去。我们引入本原多项式的概念。 Z [ x ] \mathbb{Z}[x] Z[x]上的多项式如果各项系数的最大公约数为1,则称此多项式是本原多项式。对于一个正次数有理系数多项式 g g g,在相差一个正负号的前提下可以唯一确定一个本原多项式 g 0 g_0 g0使得 g = q g 0 g=qg_0 g=qg0,其中 q q q为有理数。 c d g 0 = c ′ d ′ g 0 ′ ⇒ c d ′ g 0 = c ′ d g 0 ′ ⇒ c d ′ = ± c ′ d ⇒ g 0 = ± g 0 ′ \frac{c}{d}g_0=\frac{c^\prime}{d^\prime}g_0^\prime\Rightarrow cd^\prime g_0=c^\prime dg_0^\prime\Rightarrow cd^\prime=\pm c^\prime d\Rightarrow g_0=\pm g_0^\prime dcg0=dcg0cdg0=cdg0cd=±cdg0=±g0。由此,我们就可以得到
    f = q 1 g 1 ⋯ q n g n = q 1 ⋯ q n g 1 ⋯ g n . f=q_1g_1\cdots q_ng_n=q_1\cdots q_ng_1\cdots g_n. f=q1g1qngn=q1qng1gn.

    下面的问题在于说明前面的系数是整数。我们断言:本原多项式的乘积还是本原多项式。这里我们会看到引入商同态是必要的。设 g , h ∈ Z [ x ] g,h\in \mathbb{Z}[x] g,hZ[x]均为本原多项式,假设 g h gh gh不是本原多项式,则存在素数 p p p整除所有系数。通过商同态 Z [ x ] → Z p [ x ] \mathbb{Z}[x]\rightarrow\mathbb{Z}_p[x] Z[x]Zp[x],我们得到 g ˉ h ˉ = g h ‾ = 0 ∈ Z p [ x ] \bar g\bar h=\overline{gh}=0\in \mathbb{Z}_p[x] gˉhˉ=gh=0Zp[x]。因为 Z p [ x ] \mathbb{Z}_p[x] Zp[x]是整环,所以必定有 g ˉ = 0 \bar g=0 gˉ=0或者 h ˉ = 0 \bar h=0 hˉ=0,也就是说 p p p会整除其中一个多项式的所有系数,矛盾。当然,我们也可以直接论证。但是,正是引入了保持运算的映射,使得理解过程变得本质而自然。从这个地方,就可以意识到,不仅仅要将集合作为一个基本概念,而且还要把集合之间保持运算的映射(一般称为态射)作为基本的概念。把代数系统和态射放在一起构成范畴,这样考虑问题就更加自然。 f = c d g 1 ⋯ g n ⇒ d f = c g 1 ⋯ g n ⇒ d d ′ f 0 = c g 1 ⋯ g n f=\frac{c}{d}g_1\cdots g_n\Rightarrow df=cg_1\cdots g_n\Rightarrow dd^\prime f_0=cg_1\cdots g_n f=dcg1gndf=cg1gnddf0=cg1gn。由于本原多项式的乘积还是本原多项式,所以 f 0 = ± g 1 ⋯ g n f_0=\pm g_1\cdots g_n f0=±g1gn c = ± d d ′ c=\pm dd^\prime c=±dd

    于是分解式的存在性就迎刃而解。再看分解的唯一性。这部分就比较简单了,直接放到 Q [ x ] \mathbb{Q}[x] Q[x]中去看就能够得出来。

    抽象一下

    上面的结果可以进行抽象下。其实,任何唯一分解整环上的多项式环都是唯一分解整环。证明的过程和 Z [ x ] \mathbb{Z}[x] Z[x]的证明过程基本类似。

    说点其他的……

    上面说明了一些常见的对象是唯一因子分解整环,于是理解这个对象的主要工作就在某种意义上归结为理解不可约元。然而,我们对不可约元的理解其实是很少的。在整数环中,对素数的理解占据了数论研究的半壁江山:寻找大素数,素数的判断,素数的表达式,素数的分布。

    展开全文
  • 题目描述 ...唯一因式分解公式 n = (p1e1)(p2e2)(p3e3 ) … (pnen ) 因子数 cnt = (1+e1)(1+e2)(1+e3)…(1+en) 因子和 sum = (1+p1+p12+…+p1e1)(1+p2+p22+…+p2e2)…(1+p3+p32+…+p3e2) 代码(python) #
  • 唯一因子分解方程 每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。 标称: #include <iostream> #include <cstring> #include <cstdlib> using ...

    唯一质因子分解方程

    每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。
    标称:

    #include <iostream>
    #include <cstring>
    #include <cstdlib>
    using namespace std;
    const int MAXN = 65540;
    int a[MAXN];
    int main(){
        int n;
        while(cin >> n && n){
            int cnt = 0;
    
            for(int i=2;i<=n;++i){
                while(n % i == 0){
                    a[cnt++] = i;
                    n /= i;
                }
            }
            for(int i=0;i<cnt-1;++i){
                cout << a[i] << "*";
            }
            cout << a[cnt-1] << endl;
        }
        return 0;
    }
    

    one 试除法:无论素数判定还是因子分解,试除法(Trial Division)都是首先要进行的步骤。令m=n,从2~根n一一枚举,如果当前数能够整除m,那么当前数就是n的素数因子,并用整数m
    将当前数除尽为止。
    若循环结束后m是大于1的整数,那么此时m也是n的素数因子

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    #include <math.h>
    #define N 65535
    using namespace std;
    int factor[N],top;
    void divide(int n)
    {
        for(int i=2; i<=sqrt(n+0.0); i++)
        {
            while(n%i==0)
            {
                top++;
                factor[top]=i;
                n/=i;
            }
        }
        if(n!=1)
        {
            top++;
            factor[top]=n;
        }
        for(int i=1; i<=top-1; i++)
        {
            printf("%d*",factor[i]);
        }
        printf("%d\n",factor[top]);
        return ;
    }
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            top=0;
            divide(n);
        }
        return 0;
    }
    

    two:在试除法基础上加上筛法(埃氏筛),减少时间

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    #include <math.h>
    #define N 65540
    using namespace std;
    int factor[N],top,cnt,prime[N];
    bool b[N];
    void make_prime()
    {
        top=0;
        b[0]=b[1]=false;
        b[2]=true;
        prime[++top]=2;
        for(int i=3; i<N; i++)
            if(i%2==0) b[i]=false;
            else b[i]=true;
        double t=sqrt(1000000*1.0);
        for(int i=3; i<=t; i++)
        {
            if(b[i])
            {
                prime[++top]=i;
                for(int j=i*i; j<N; j=j+i)
                {
                    b[j]=false;
                }
            }
        }
    }
    void divide(int n)
    {
        cnt=0;
        int temp=sqrt(n+0.0);
        for(int i=1; i<=top; i++)
        {
            if(prime[i]>temp)
                break;
            while(n%prime[i]==0)
            {
                cnt++;
                factor[cnt]=prime[i];
                n/=prime[i];
            }
        }
        if(n!=1)
        {
            cnt++;
            factor[cnt]=n;
        }
        for(int i=1; i<=cnt-1; i++)
        {
            printf("%d*",factor[i]);
        }
        printf("%d\n",factor[cnt]);
        return ;
    }
    int main()
    {
        int n;
        make_prime();
        while(scanf("%d",&n)!=EOF)
        {
            divide(n);
        }
        return 0;
    }
    
    展开全文
  • 阶乘质因子分解唯一分解定理)

    千次阅读 2016-09-11 08:35:44
    阶乘质因子分解题目描述: 对N!进行质因子分解。 输入输出格式: 输入格式: 输入数据仅有一行包含一个正整数N,N。 输出格式: 输出数据包含若干行,每行两个正整数p,a,中间用一个空格隔开。表示N!包含a个质...
  • CCCC-GPLT 练习赛 7-15 素因子分解 (20 分)素数筛+唯一分解定理 7-15 素因子分解 (20 分) 给定某个正整数 N,求其素因子分解结果,即给出其因式分解表达式. 输入格式: 输入long int范围内的正整数 N。 输出格式...
  • 逻辑回归无法学习到特征间的组合关系,因此有了 因子分解机FM 和 场感知因子分解机FFM。 接下来,介绍下场感知因子分解机的主要应用。FFM模型可以自动做特征组合和处理高维稀疏特征,因而它在处理大量离散特征问题...
  • 题目解析方法一:质因子分解+线性筛+唯一分解定理 1. 题目来源 链接:UVA10375 Choose and divide 2. 题目说明 中文描述: 3. 题目解析 方法一:质因子分解+线性筛+唯一分解定理 这真是一道纯数学题目了,不需要...
  • 1.唯一分解定理,也叫算术基本定理,指的是任何n>=2,都可以分解为n=p1* p2 * p3 * … * pn,其中pi为质数。 其包括两个断言: 断言1:数n可以以某种方式分解成素数乘积。 断言2:仅有一种这样的因数分解。(除...
  • 选择与除法 已知C(m,n) =m!/(n!(m-n)!),输入整数p, q,1,s ( p=q , r2s , p.q ,7,s≤10000 ) ,计算C(p,q)/C(r,s)。输出保证不超过108,保留5位小数。...阶乘质因子分解公式:N的阶乘的质因子m的指数:X
  • 因子分解

    2015-08-02 20:10:26
    因子分解 Description 假设x是一个正整数,它的值不超过65535(即1 Input 输入的第一行含一个正整数k (1 Output 每个测试例对应一行输出,输出x的素数乘积表示式,式中的素数从小到大排列,两个素数之间用...
  • 因子分解与域的扩展 一、因子分解 我们知道,整数环中的每一个合数都可以唯一地分解成素数的乘积; 域 F 上每个次数大于零的可约多项式,都可以唯一地分解成不可约多项式的乘积。这是整数环和多项式环中元素的最基本...
  • 唯一分解定理:每个大于一的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法只有一种方式。 最简单的写法: #include &lt;iostream&gt; #include &lt;cstring&gt; #include &...
  • 因子分解 模板

    2016-08-08 00:40:34
    唯一分解定理的模板
  • 唯一分解定理】 又称算术基本定理,可以描述为:任意一个大于1的正整数都能表示成若干个质数的乘积,且表示的方法是唯一的。换句话说,一个数能被唯一分解成质因数的乘积。 公式:, 因子数: p1可以取的...
  • 思路:由于质因子分解唯一的(算术基本定理),因此只需要枚举质因子(提前打表质数),计数即可。 AC code: #include<bits/stdc++.h> using namespace std; const int maxn=100000; struct fac{ int x,...
  • 因子分解

    千次阅读 2018-09-28 23:33:10
    也可以说是一个数学定义吧:任何一个大于1的自然数N,如果N不为质数,那么N可以分解 成有限个质数的乘积,并且在不计次序的情况下,这种分解 方式是唯一的。  就是随便给你一个非质数,我们都可以用几个质数的乘积...
  • 输出 N的个位数 样例输入 1 1 2 6 1 3 1 1 1 1 1 样例输出 9 题目分析: 唯一因子分解问题,对于任意一个数n,都可以表示为:n=p[0]^a[0]*......*p[i]^a[i]*......*p[n]^a[n],其中p[i]是素数,a[i]是整数>0,而n...
  • 与矩阵因子分解相比,因子分解机本质上是更通用的。我们常见的问题表述本身是非常不同的,它被公式化为线性模型,特征之间的交互作用作为附加参数。此功能交互以其潜在空间标识而不是其纯格式完成。因此,除了像矩阵...
  • P2043 质因子分解

    2018-07-16 11:20:00
    P2043 质因子分解 题目描述 对N!进行质因子分解。 输入输出格式 输入格式: 输入数据仅有一行包含一个正整数N,N<=10000。 输出格式: 输出数据包含若干行,每行两个正整数p,a,中间用一个空格隔开。表示N!包含a...
  • 唯一分解定理】:https://www.cnblogs.com/mjtcn/p/6743624.html 假设x是一个正整数,它的值不超过65535(即1<x<=65535),请编写一个程序,将x分解为若干个素数的乘积。 Input 输入的第一行含一个正整数k ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,962
精华内容 6,384
关键字:

唯一因子分解