基于题目的：求大数因子
程序员文章站
2022-03-23 09:20:12
...
资料来源：
1，https://blog.csdn.net/tomorrowtodie/article/details/51865496
2，https://blog.csdn.net/Danliwoo/article/details/48827813#fn:meison
3，https://blog.csdn.net/u012717411/article/details/43412043
4，https://blog.csdn.net/z690933166/article/category/1349672/3
5，https://blog.csdn.net/lianai911/article/category/2562225/4
6，https://blog.csdn.net/bigbigship/article/category/1931643/6
7，http://www.cnblogs.com/tom987690183/p/3260724.html
题型：求大数因子
整数分解用的是Pollard rho算法,可以求2^63以内的数分解成素因子
模板是直接copy的kuangbin的模板（蛮长）
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<iostream>
#include<algorithm>
using namespace std;
//****************************************************************
// Miller_Rabin 算法进行素数测试
//速度快，而且可以判断 <2^63的数
//****************************************************************
const int S=20;//随机算法判定次数，S越大，判错概率越小
//计算 (a*b)%c. a,b都是long long的数，直接相乘可能溢出的
// a,b,c <2^63
long long mult_mod(long long a,long long b,long long c)
{
a%=c;
b%=c;
long long ret=0;
while(b)
{
if(b&1){ret+=a;ret%=c;}
a<<=1;
if(a>=c)a%=c;
b>>=1;
}
return ret;
}
//计算 x^n %c
long long pow_mod(long long x,long long n,long long mod)//x^n%c
{
if(n==1)return x%mod;
x%=mod;
long long tmp=x;
long long ret=1;
while(n)
{
if(n&1) ret=mult_mod(ret,tmp,mod);
tmp=mult_mod(tmp,tmp,mod);
n>>=1;
}
return ret;
}
//以a为基,n-1=x*2^t a^(n-1)=1(mod n) 验证n是不是合数
//一定是合数返回true,不一定返回false
bool check(long long a,long long n,long long x,long long t)
{
long long ret=pow_mod(a,x,n);
long long last=ret;
for(int i=1;i<=t;i++)
{
ret=mult_mod(ret,ret,n);
if(ret==1&&last!=1&&last!=n-1) return true;//合数
last=ret;
}
if(ret!=1) return true;
return false;
}
// Miller_Rabin()算法素数判定
//是素数返回true.(可能是伪素数，但概率极小)
//合数返回false;
bool Miller_Rabin(long long n)
{
if(n<2)return false;
if(n==2)return true;
if((n&1)==0) return false;//偶数
long long x=n-1;
long long t=0;
while((x&1)==0){x>>=1;t++;}
for(int i=0;i<S;i++)
{
long long a=rand()%(n-1)+1;//rand()需要stdlib.h头文件
if(check(a,n,x,t))
return false;//合数
}
return true;
}
//************************************************
//pollard_rho 算法进行质因数分解
//************************************************
long long factor[100];//质因数分解结果（刚返回时是无序的）
int tol;//质因数的个数。数组小标从0开始
long long gcd(long long a,long long b)
{
if(a==0)return 1;//???????
if(a<0) return gcd(-a,b);
while(b)
{
long long t=a%b;
a=b;
b=t;
}
return a;
}
long long Pollard_rho(long long x,long long c)
{
long long i=1,k=2;
long long x0=rand()%x;
long long y=x0;
while(1)
{
i++;
x0=(mult_mod(x0,x0,x)+c)%x;
long long d=gcd(y-x0,x);
if(d!=1&&d!=x) return d;
if(y==x0) return x;
if(i==k){y=x0;k+=k;}
}
}
//对n进行素因子分解
void findfac(long long n)
{
if(Miller_Rabin(n))//素数
{
factor[tol++]=n;
return;
}
long long p=n;
while(p>=n)p=Pollard_rho(p,rand()%(n-1)+1);
findfac(p);
findfac(n/p);
}
int main()
{
//srand(time(NULL));//需要time.h头文件//POJ上G++不能加这句话
long long n;
while(scanf("%I64d",&n)!=EOF)
{
tol=0;
findfac(n);
for(int i=0;i<tol;i++)printf("%I64d ",factor[i]);
printf("\n");
if(Miller_Rabin(n))printf("Yes\n");
else printf("No\n");
}
return 0;
}
我介里有学长的稍微短点的代码，嘿嘿嘿。。。
资料来源2：https://blog.csdn.net/
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<stdlib.h>
#include<time.h>
#define times 20
using namespace std;
long long total;
long long factor[110];
long long qmul(long long a,long long b,long long M){
a%=M;
b%=M;
long long ans=0;
while (b){
if (b&1){
ans=(ans+a)%M;
}
a=(a<<=1)%M;
b>>=1;
}
return ans%M;
}//快乘，因为两个longlong的数相乘可能会溢出，所以这里转乘法为加法，思想和快速幂相似
long long qpow(long long a,long long b,long long int M){
long long ans=1;
long long k=a;
while(b){
if(b&1)ans=qmul(ans,k,M)%M;
k=qmul(k,k,M)%M;
b>>=1;
}
return ans%M;
}//快速幂
bool witness(long long a,long long n,long long x,long long sum){
long long judge=qpow(a,x,n);
if (judge==n-1||judge==1)return 1;
while (sum--){
judge=qmul(judge,judge,n);
if (judge==n-1)return 1;
}
return 0;
}
bool miller(long long n){
if (n<2)return 0;
if (n==2)return 1;
if ((n&1)==0)return 0;
long long x=n-1;
long long sum=0;
while (x%2==0){
x>>=1;
sum++;
}
for (long long i=1;i<=times;i++){
long long a=rand()%(n-1)+1;
if (!witness(a,n,x,sum))return 0;//费马小定理的随机数检验
}
return 1;
}//判断一个数是否为素数
long long gcd(long long a,long long b){
return b==0?a:gcd(b,a%b);
}//欧几里得算法
long long pollard(long long n,long long c){
long long x,y,d,i=1,k=2;
x=rand()%n;
y=x;
while (1){
i++;
x=(qmul(x,x,n)+c)%n;
d=gcd(y-x,n);
if (d<0)d=-d;
if (d>1&&d<n)return d;
if (y==x)return n;
if (i==k){
y=x;
k<<=1;
}
}
}
void find(long long n){
if (miller(n)){
factor[++total]=n;
return ;
}
long long p=n;
while (p>=n){
p=pollard(p,rand()%(n-1)+1);
}
find(n/p);
find(p);
}//寻找这个数的素因子，并存起来
int main(){
long long n,m,i,t;
scanf("%lld",&t);
while (t--){
scanf("%lld",&n);
if (miller(n)){
printf("Prime\n");
}
else {
memset(factor,0,sizeof(factor));
total=0;
find(n);
sort(factor+1,factor+total+1);
printf("%lld\n",factor[1]);
}
}
}
//素数测试的代码
//作用：判断一个数是否是素数，如果是，输出Prime，反之输出最小的素因子
来看一道题：
整数分解也有个题：GCD & LCM Inverse（用dfs去找答案）
GCD & LCM Inverse
Description
Given two positive integers a and b, we can easily calculate the greatest common divisor (GCD) and the least common multiple (LCM) of a and b. But what about the inverse? That is: given GCD and LCM, finding a and b.
Input
The input contains multiple test cases, each of which contains two positive integers, the GCD and the LCM. You can assume that these two numbers are both less than 2^63.
Output
For each test case, output a and b in ascending order. If there are multiple solutions, output the pair with smallest a + b.
Sample Input
3 60
Sample Output
12 15
Source
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<cmath>
#include<stdlib.h>
#include<cctype>
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef unsigned long long ll;
const int S = 20;
ll mult_mod (ll a, ll b, ll c)
{
a %= c, b %= c;
ll ret = 0;
ll tmp = a;
while (b)
{
if (b & 1)
{
ret += tmp;
if (ret > c) ret -= c;
}
tmp <<= 1;
if (tmp > c) tmp -= c;
b >>= 1;
}
return ret;
}
ll pow_mod (ll a, ll n, ll mod)
{
ll ret = 1;
ll temp = a % mod;
while (n)
{
if (n & 1) ret = mult_mod (ret, temp, mod);
temp = mult_mod (temp, temp, mod);
n >>= 1;
}
return ret;
}
bool check (ll a, ll n, ll x, ll t)
{
ll ret = pow_mod (a, x, n);
ll last = ret;
for (int i = 1; i <= t; ++i)
{
ret = mult_mod (ret, ret, n);
if (ret == 1 && last != 1 && last != n - 1) return 1;
last = ret;
}
if (ret != 1) return 1;
else return 0;
}
bool MR (ll n)
{
if (n < 2) return 0;
if (n == 2) return 1;
if ( (n & 1) == 0) return 0;
ll x = n - 1;
ll t = 0;
while ( (x & 1) == 0)
{
x >>= 1;
++t;
}
// srand(time(NULL));
for (int i = 0; i < S; ++i) //做S次测试
{
ll a = rand() % (n - 1) + 1;
if (check (a, n, x, t) ) return 0; //只要其中有一次判定是合数就可以确定一定是合数
}
return 1;
}
ll fac[11111];//质因数分解结果(刚返回时时无序的)
int tot;//质因数的个数，数组下标从0开始
ll gcd (ll a, ll b)
{
if (a == 0) return 1;
if (a < 0) return gcd (-a, b);
while (b)
{
ll t = a % b;
a = b, b = t;
}
return a;
}
ll PR (ll x, ll c)
{
ll i = 1, k = 2;
ll x0 = rand() % x;
ll y = x0;
while (1) //美丽的循环，不会死
{
++i;
x0 = (mult_mod (x0, x0, x) + c) % x;
ll d = gcd (y - x0, x);
if (d != 1 && d != x) return d;
if (y == x0) return x;
if (i == k)
{
y = x0;
k += k;
}
}
}
void findfac (ll n) //对n进行素因子分解
{
if (MR (n) ) //如果n是素数
{
fac[tot++] = n;
return;
}
ll p = n;
while (p >= n) p = PR (p, rand() % (n - 1) + 1);
findfac (p);
findfac (n / p);
}
ll x[111];
ll k;
ll a, b, mn;
ll ans;
ll g, lcm;
const ll inf = 1LL << 62LL;
bool fd;
void dfs (ll cur, ll p)
{
ll q = ans / p;
if (gcd (p, q) == 1)
{
fd = 1;
ll tmp = p * g + q * g;
if (mn > tmp)
{
mn = tmp;
a = p*g;
b = q*g;
}
}
if (cur > k) return;
dfs(cur+1,p);p*=x[cur];
if (p > mn ) return ;
dfs(cur+1,p);
}
int main()
{
while (~scanf ("%llu %llu", &g, &lcm) )
{
if (g == lcm)
{
printf("%llu %llu\n",g,lcm);
continue;
}
ans = lcm / g;
tot = 0;
// cout << ans << endl;
findfac (ans);
sort (fac, fac + tot); //fac保存的是ans的素因子，比如3 60对应的fac数组是2 2 5
// for (int i = 0; i < tot; ++i) cout << fac[i] << " ";
// cout << "---------------------------------------------------" << endl;
k = 0;
x[0] = fac[0];
for (int i = 1; i < tot; ++i)
{
if (fac[i] == fac[i - 1]) x[k] *= fac[i];
else x[++k] = fac[i];
}
sort (x, x + k + 1); //x保存的是所有不相同的素因子，比如3 60 对应的x数组是4 5
// for (int i = 0; i <= k; ++i) cout << x[i] << " ";
// cout << endl;
//用dfs将数组x分成2部分p*q,满足p,q互质,找到所有p,q中使a+b最小的情况，其中a = p*lcm,b = q*lcm
//比如3 60 ans = 20 4 5 ,a = 4*3 b = 5*3
mn = inf;
fd = 0;
dfs (0, 1);
if (a > b) swap (a, b);
// if (!fd) puts ("???");
printf ("%llu %llu\n", a, b);
}
return 0;
}
/*
7 635040
*/
整数分解
将整数化为质因子的幂的乘积的唯一形式。常用试除法、筛选法，比较简单不举例了。对于非常大的数而言，两者用处不大。
Pollard ρρ 整数分解法
原理还不太懂：
1. 生成两个整数a、b，计算p=(a-b,n)，直到p不为1或a,b出现循环为止。
2. 若p=n，则n为质数；否则为n的一个约数。
分解n的具体步骤如下：
//找出一个因子
LL pollard_rho(LL x,LL c)
{
LL i = 1, k = 2;
srand(time(NULL));
LL x0 = rand()%(x-1) + 1;
LL y = x0;
while(1)
{
i++;
x0 = (mult_mod(x0,x0,x) + c)%x;//迭代公式为(x0*x0+c)%x
LL d = gcd(y - x0,x);//gcd返回一个绝对值
if( d != 1 && d != x)
return d;
if(y == x0)
return x;
if(i == k)
{
y = x0;
k += k;
}
}
}
//对n进行素因子分解，存入factor. k设置为107左右即可
void findfac(LL n,int k)
{
if(n == 1)
return;
if(Miller_Rabin(n))
{
factor[tol++] = n;
return;
}
LL p = n;
int c = k;
while( p >= n)
p = pollard_rho(p,c--);//c即k表示最大搜索次数？
//值变化，防止死循环k
findfac(p,k);
findfac(n/p,k);
}如：http://icpc.njust.edu.cn/Problem/Pku/1811/
http://icpc.njust.edu.cn/Problem/Pku/2429/
素因子分解&&素因子分解求最大公约数&&素因子分解求最小公倍数
素因子分解 就是把一个数化成 n=p1^a1*p2^a2*.....*pn^an的形式 其中p1,p2...pn都为素数；
#include <iostream>//整数素因子分解
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
int n;
while(cin>>n){
int x,count1=0;
int tn=n;
int count2=0;
for(int i=2;i<=n;i++){
if(tn%i==0){
count1=0;
++count2;
while(tn%i==0){
count1++;
tn/=i;
}
cout<<"素因子 "<<i<<" 幂指数"<<count1<<endl;
}
}
cout<<"素因子个数 "<<count2<<endl;
}
return 0;
}
素因子分解法求最小公倍数&最大公约数；
a=(p1^a1)*(p2^a2)*(p3^a3)…(pm^am),b=(p1^b1)*(p2^b2)*(p3^b3)…(pm^bm)
其中最小公倍数=max(ai,bi); 最大公约数=min(ai,bi);
下面是求最大公约数的方法：
//素因子分解求最小公倍数
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
int main()
{
ll n,m;
while(cin>>n>>m){
int tn=n,tm=m;
int count1,count2;
ll lcm=1;
ll mult1=1,mult2=1;
for(int i=2;i<=max(n,m);i++){
if(tn%i==0||tm%i==0){
count1=count2;
mult1=mult2=1;
while(tn%i==0){
count1++;
tn/=i;
mult1*=i;
}
while(tm%i==0){
count2++;
tm/=i;
mult2*=i;
}
lcm=lcm*max(mult1,mult2);
}
}
printf("%lld\n",lcm);
}
return 0;
}
POJ1365 Prime Land【质因数分解】【素数】【水题】
2014年09月17日 09:16:05
阅读数：1746
题目链接：
http://poj.org/problem?id=1365
题目大意：
告诉你一个数的质因数x的所有底数pi和幂ei，输出x-1的质因数的所有底数和幂
解题思路：
这道题不难，但是题意特别不好理解，对于我这种英文渣的人，愣是一个小时没看明白
关于题意举例说明吧
例如 509 1 59 1
x = 509^1 * 59^1 = 30031
x-1 = 30030
则答案 13 1 11 1 7 1 5 1 3 1 2 1 就是 x-1 = 13^1 * 11^1 * 7^1 * 5^1 *3^1 *2^1
= 30031
那么直接按着题意暴力解决就行了。。。。。
AC代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
/*
pow函数说明
原型：extern float pow(float x, float y);
用法：#include <math.h>
功能：计算x的y次幂。
说明：x应大于零，返回幂指数的结果。
*/
double p[110],e[110];
int Prime[35000],E[35000];
void IsPrime()
{
Prime[0] = Prime[1] = 0;
for(int i = 2; i <= 35000; i++)
{
Prime[i] = 1;
}
for(int i = 2; i <= 35000; i++)
{
for(int j = i+i; j <= 35000; j+=i)
{
Prime[j] = 0;
}
}
}
int main()
{
int count,sign;
IsPrime();
// for(int i = 2; i <= 35000; i++)
// if(Prime[i])
// printf("%d ",i);
while(1)
{
count = 0,sign = 0;
memset(p,0,sizeof(p));
memset(e,0,sizeof(e));
memset(E,0,sizeof(E));
while(1)
{
scanf("%lf",&p[count]);
if(p[count] == 0)
{
sign = 1;
break;
}
scanf("%lf",&e[count]);
count++;
char c = getchar();
if(c=='\n')
break;
}
if(sign == 1)
break;
double num = 1;
for(int i = 0; i < count; i++)
num *= pow(p[i],e[i]);
int sum = (int)num - 1;
// printf("%d\n",sum);
int flag = 0,pos = 2;
for(int i = 2; i <= 32767; i++)
{
if(sum == 1)
break;
if(Prime[i])
{
while(sum % i == 0)
{
E[i]++;
sum /= i;
if(flag == 0)
{
flag = 1;
pos = i;
}
}
}
}
for(int i = 32767; i>= 2; i--)
{
if(E[i]!=0 && i!=pos)
printf("%d %d ",i,E[i]);
else if(E[i]!=0 && i==pos)
{
printf("%d %d\n",i,E[i]);
break;
}
}
}
return 0;
}zoj 3286 Very Simple Counting---统计[1，N]相同因子个数
Very Simple Counting
Let f(n) be the number of factors of integer n.
Your task is to count the number of i(1 <= i < n) that makes f(i) = f(n).
Input
One n per line (1 < n <= 1000000).
There are 10000 lines at most.
Output
For each n, output counting result in one line.
Sample Input
4 5
Sample Output
0 2
Hint
f(1) = 1, f(2) = f(3) = f(5) = 2, f(4) = 3.
Author: WU, Jun
Source: ZOJ Monthly, December 2009
理论依据：
zoj的题目，对时间和空间的要求都很高。
这一题，首先做的时候，超时。
不看时间，不看数据，直接枚举，不超时是不可能。
根据的公式和上一题福州大学oj那一题是一样的。
#include<iostream>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
bool s[1000003];
int num[1000003];
int ans[1000003];//个数
int f[1000003];
map<int,int>Q;
void make_ini()
{
int i,j,k;
for(i=1;i<=1000000;i++)
{
num[i]=i;
ans[i]=1;
f[i]=0;
}
for(i=2;i<=1000000;i++)
if(s[i]==false)//是素数
{
for(j=i;j<=1000000;j=j+i)//枚举每个素数的倍数
{
// if(j%i==0) //这个肯定成立，不需要
{
k=1;
while(num[j]%i==0)
{
num[j]=num[j]/i;
k++;
}
ans[j]=ans[j]*k;
}
s[j]=true;
}
}
for(i=1;i<=1000000;i++)
{
k=ans[i];
if(Q.find(k)==Q.end())
{
Q[k]=1;
}
else Q[k]++;
f[i]=Q[k];
}
}
int main()
{
int n;
make_ini();
// Q.clear();
while(scanf("%d",&n)>0)
{
printf("%d\n",f[n]-1);
}
return 0;
}
上一篇： 奇异值分解（SVD）及其应用
下一篇： Python编程之正整数分解