整数分解,又称质因子分解.在数学中,整数分解问题是指:给出一个正整数,将其写成几个素数的乘积的形式. (每个合数都可以写成几个质数相乘的形式,这几个质数就都叫做这个合数的质因数.) .试除法(适用于范围比较小) 无论素数判定还是因子分解,试除法(Trial Division)都是首先要进行的步骤.令m=n,从2~根n一一枚举,如果当前数能够整除m,那么当前数就是n的素数因子,并用整数m 将当前数除尽为止. 若循环结束后m是大于1的整数,那么此时m也是n的素数因子. 事例如HDU1164:15mm

\(\\\) Miller-Rabin 素性测试 考虑如何检验一个数字是否为素数. 经典的试除法复杂度 \(O(\sqrt N)\) 适用于询问 \(N\le 10^{16}\) 的时候. 如果我们要把询问范围加到 \(10^{18}\) ,再多组询问呢? Miller 和 Rabin 建立了Miller-Rabin 质数测试算法. \(\\\) Fermat 测试 首先我们知道费马小定理: \[ a^{p-1}\equiv 1\pmod p \] 当且仅当 \(p\) 为素数时成立. 逆命题是

题意: 考虑所有满足2 ≤ a ≤ 5和2 ≤ b ≤ 5的整数组合生成的幂ab: 22=4, 23=8, 24=16, 25=3232=9, 33=27, 34=81, 35=24342=16, 43=64, 44=256, 45=102452=25, 53=125, 54=625, 55=3125 如果把这些幂按照大小排列并去重,我们得到以下由15个不同的项组成的序列: 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 31

13:大整数的因子 总时间限制:  1000ms 内存限制:  65536kB 描述 已知正整数k满足2<=k<=9,现给出长度最大为30位的十进制非负整数c,求所有能整除c的k. 输入 一个非负整数c,c的位数<=30. 输出 若存在满足 c%k == 0 的k,从小到大输出所有这样的k,相邻两个数之间用单个空格隔开:若没有这样的k,则输出"none". 样例输入 30 样例输出 2 3 5 6 思路: 模拟: 来,上代码: #include<cstdio&g

题意:给出一个N,若N为素数,输出Prime.若为合数,输出最小的素因子.思路:Pollard rho大整数分解,模板题 #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <cstdlib> #include <cmath> using namespace std; long long n; long lon

BUPT2017 wintertraining(15) #8E 题意 长度为n(\(n<2^{63}\))的绳子,每隔长度L(1<L<n)做一次标记,标记值就是L,L是n的约数. 每轮标记都选一个L,且L之间两两互质. 求L的最多种数K.以及标记之和S的最大值. 题解 对n进行分解质因数,K就是不同质因子的个数,S就是p^{a_i}之和.不过题目要求L<n,所以当S算出来是n时,再除以一下最小的质因子. 分解比较小的n(<1e9),可以直接枚举,复杂度是\(O(\sqrt n

大整数的因子 总时间限制:  1000ms 内存限制:  65536kB 描述 已知正整数k满足2<=k<=9,现给出长度最大为30位的十进制非负整数c,求所有能整除c的k. 输入 一个非负整数c,c的位数<=30. 输出 若存在满足 c%k == 0 的k,从小到大输出所有这样的k,相邻两个数之间用单个空格隔开:若没有这样的k,则输出"none". 样例输入 30 样例输出 2 3 5 6 代码 高精模运算 #include<iostream> #inc

时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:974 解决:494 题目描述: 已知正整数k满足2<=k<=9,现给出长度最大为30位的十进制非负整数c,求所有能整除c的k. 输入: 若干个非负整数c,c的位数<=30 每行一个c,当c=-1时中止 (不要对-1进行计算!) 输出: 每一个c的结果占一行 1) 若存在满足 c%k == 0 的k,输出所有这样的k,中间用空格隔开,最后一个k后面没有空格. 2) 若没有这样的k则输出"none" 样例输入:

啊居然要特判,卡了好久QAQ (好像Windows下的rand和Linux下的不一样? QwQ一些东西参考了喵铃的这篇blog:http://www.cnblogs.com/meowww/p/6400841.html  (业界良心) 题目 题意:输入$n$,求$phi(n)$,$n \leq 10^{18}$ 随便抽的题,刚好学习一下相关的算法. 很明显朴素的根号算法时间复杂度补滋兹,线性筛更不用想了,不过这题只需要单个欧拉函数值,还是直接考虑$phi(n)=n*\prod_{i=1}^k(1-

题目是POJ1001 Exponentiation  虽然是小数的幂 最终还是转化为大整数的乘法 这道题要考虑的边界情况比较多 做这道题的时候,我分析了 网上的两个解题报告,发现都有错误,说明OJ对于错误的判断还不够严厉. 对边界情况的讨论其实应该是思维严密的表现,当然这并不能表明我写的一点错误都没有,只是多多分析一下还是很有好处的. #include <iostream> #include <fstream> #include <string> #include &l

/* codevs 3119 高精度练习之大整数开根 (各种高精+压位) 二分答案 然后高精判重 打了一个多小时..... 最后还超时了...压位就好了 测试点#1.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms 测试点#2.in 结果:AC 内存使用量: 256kB 时间使用量: 1ms 测试点#3.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms 测试点#4.in 结果:AC 内存使用量: 256kB 时间使用量: 10ms 测试点#5.in 结果:AC 内

★ 引子         前面两篇介绍了 Comba 乘法,最后提到当输入的规模很大时,所需的计算时间会急剧增长,因为 Comba 乘法的时间复杂度仍然是 O(n^2).想要打破乘法中 O(n^2) 的限制,需要从一个完全不同的角度来看待乘法.在下面的乘法算法中,需要使用 x 和 y 这两个大整数的多项式基表达式 f(x) 和 g(x) 来表示. 令 f(x) = a * x + b,g(x) = c * x + d,h(x) = f(x) * g(x).这里的 x 相当于一个基,比如十进制下,

算法课有这么一节,专门介绍分治法的,上机实验课就是要代码实现大整数乘法.想当年比较混,没做出来,颇感遗憾,今天就把这债还了吧! 大整数乘法,就是乘法的两个乘数比较大,最后结果超过了整型甚至长整型的最大范围,此时如果需要得到精确结果,就不能常规的使用乘号直接计算了.没错,就需要采用分治的思想,将乘数“分割”,将大整数计算转换为小整数计算. 在这之前,让我们回忆一下小学学习乘法的场景吧.个位数乘法,是背诵乘法口诀表度过的,不提也罢:两位数乘法是怎么做的呢?现在就来一起回忆下12*34吧:    3 

最近在跟coursera上斯坦福大学的算法专项课,其中开篇提到了两个整数相乘的问题,其中最简单的方法就是模拟我们小学的整数乘法,可想而知这不是比较好的算法,这门课可以说非常棒,带领我们不断探索更优的算法,然后介绍可以通过使用分而治之的思想来解决这个问题.下面对该问题的方法以及实现进行介绍. 问题定义 输入:2个n位的整数x和y 输出:x * y 如求: 1234567891011121314151617181*2019181716151413121110987654 的结果 求解该问题要注意的是

★ 引子         前面两篇介绍了 Comba 乘法,最后提到当输入的规模很大时,所需的计算时间会急剧增长,因为 Comba 乘法的时间复杂度仍然是 O(n^2).想要打破乘法中 O(n^2) 的限制,需要从一个完全不同的角度来看待乘法.在下面的乘法算法中,需要使用 x 和 y 这两个大整数的多项式基表达式 f(x) 和 g(x) 来表示. 令 f(x) = a * x + b,g(x) = c * x + d,h(x) = f(x) * g(x).这里的 x 相当于一个基,比如十进制下,

随机拆分,简直机智. 关于过程可以看http://wenku.baidu.com/link?url=JPlP8watmyGVDdjgiLpcytC0lazh4Leg3s53WIx1_Pp_Y6DJTC8QkZZqmiDIxvgFePUzFJ1KF1G5xVVAoUZpxdw9GN-S46eVeiJ6Q-zXdei 看完后,觉得随机生成数然后和n计算gcd,可以将随机的次数根号一下.思想很叼. 对于里面说的birthday trick,在执行次数上我怎么看都只能减一半.只是把平均分布,变成了靠近0

一,题意: 大整数乘法模板题二,思路: 1,模拟乘法(注意"逢十进一") 2,倒序输出(注意首位0不输出) 三,步骤: 如:555 x 35 = 19425  5 5 5  5 5 5 x   3 5 x    3 5 -----------   ==>    ----------   2 7 7 5 25 25 25    + 1 6 6 5   +15 15 15 -------------  -----------------    1 9 4 2 5 15 40 40 2

11:大整数减法 总时间限制:  1000ms 内存限制:  65536kB 描述 求两个大的正整数相减的差. 输入 共2行,第1行是被减数a,第2行是减数b(a > b).每个大整数不超过200位,不会有多余的前导零. 输出 一行,即所求的差. 样例输入 9999999999999999999999999999999999999 9999999999999 样例输出 9999999999999999999999990000000000000 思路: 模拟: 来,上代码: #include<s

10:大整数加法 总时间限制:  1000ms 内存限制:  65536kB 描述 求两个不超过200位的非负整数的和. 输入 有两行,每行是一个不超过200位的非负整数,可能有多余的前导0. 输出 一行,即相加后的结果.结果里不能有多余的前导0,即如果结果是342,那么就不能输出为0342. 样例输入 22222222222222222222 33333333333333333333 样例输出 55555555555555555555 来源 程序设计实习2007 思路: 模拟: 来,上代码:

描述 一个房间里有n盏灯泡,一开始都是熄着的,有1到n个时刻,每个时刻i,我们会将i的倍数的灯泡改变状态(即原本开着的现将它熄灭,原本熄灭的现将它点亮),问最后有多少盏灯泡是亮着的. 提示 范围:40%的数据保证,n<=maxlongint 100%的数据保证,n<=10^200 ********************************************************************** 1.编个小程序,打表(1-30),可以看出规律         f(n)=

进制转换 + 大整数取模一,题意: 在b进制下,求p%m,再装换成b进制输出. 其中p为b进制大数1000位以内,m为b进制数9位以内二,思路: 1,以字符串的形式输入p,m; 2,转换:字符串->整数 十进制->b进制; 3,十进制下计算并将整形结果转换成字符串形式,并倒序储存; 4,输出.三,步骤: 1,输入p[],m[]; 2,字符串->整形 + 进制->b进制: i,进制转换语句:m2 = m2*b + m[j]-'0'; ii,大整数取模,大整数可以写成这样的形式: 12