先附上所有因数的求法:
我的做法:是今天误打误撞写出来的;
http://exam./problem.php?id=5062
然后,我上网找居然没有人写一个高效一点的,我这个做法其实就是.
不一定要会比根号N快,但是
模拟求所有因子个数的做法:
大家知道为什么所有因子的个数为:
设P1,P2……Pn都是数的质因子,
设C1,C2……Cn是数的质因子的个数:
Ans=(C1+1)*(C2+1)*……*(Cn+1)
大家想知道模拟一下就知道为什么了。
比如120=2*2*2*3*5;
那么Ans=(3+1)*(1+1)*(1+1)
要是求它的因子那么就是:
(1+2+4+8)*(1+3)*(1+5)
=(1+2+4+8)+(3+6+12+24)+(5+10+20+40)+(15+30+60+120)
其中所有因数为:
1 , 2 , 3 , 4 , 5 , 6 , 8 , 10 , 12 , 15 , 20 , 24 , 30 , 40 , 60 , 120
因数之和就是
=(1+2+4+8)+(3+6+12+24)+(5+10+20+40)+(15+30+60+120)
大家琢磨琢磨为什么是这样。
#include<bits/stdc++.h>using namespace std;const int N=5e6+10;typedef long long ll;ll qpow(ll a,ll b){ll ans=1;while(b){if(b&1){ans=ans*a;}a=a*a;b>>=1;}return ans;}/*(2*3*5*7*11)*(13*17*19*23*29)*(31*37*41*43*47)=614,88978,25884,91410前15个质数相乘得到一个 6 e18的数字*/vector<ll>v[20];map<ll,int>Vis;ll a[N],cnt,Type;void dfs(ll x,int step){if(Vis[x]==0&&step==Type){Vis[x]=1;a[cnt++]=x;return ;}for(int i=0;i<v[step].size();i++){dfs(x*v[step][i],step+1);}}void solve(){ll n;scanf("%lld",&n);cnt=0;for(int i=0;i<20;i++){v[i].clear();}Type=0;Vis.clear();for(ll i=2;i*i<=n;i++){if(n%i==0){int D=0;while(n%i==0){D++;n/=i;}for(int j=0;j<=D;j++){v[Type].push_back(qpow(i,j));}Type++;}}if(n!=1){v[Type].push_back(1);v[Type].push_back(n);Type++;}dfs(1,0);sort(a,a+cnt);for(int i=0;i<cnt;i++){printf("%lld%c",a[i],i==cnt-1?'\n':' ');}}int main(){int T;scanf("%d",&T);while(T--){solve();}return 0;}
归纳总结一下:质因数分解更快的做法:
1589: 题目名称:分解质因数
时间限制: 1 Sec内存限制: 128 MB
题目描述
求出区间[a,b]中所有整数的质因数分解。
输入
输入两个整数a,b。
输出
每行输出一个数的分解,形如k=a1*a2*a3...(a1<=a2<=a3...,k也是从小到大的)(具体可看样例)
样例输入
3 10
样例输出
3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5
提示
先筛出所有素数,然后再分解。
数据规模和约定
2<=a<=b<=10000
#include<bits/stdc++.h>using namespace std;const int N=100;typedef long long ll;ll a[N],cnt;void solve(ll n){ll tn=n;cnt=0;for(ll i=2;i*i<=n;i++){if(n%i==0){int D=0;while(n%i==0){D++;n/=i;a[cnt++]=i;}}}if(n!=1){a[cnt++]=n;}sort(a,a+cnt);printf("%lld=",tn);for(int i=0;i<cnt;i++){printf("%lld%c",a[i],i==cnt-1?'\n':'*');}}int main(){ll n,m;scanf("%lld%lld",&n,&m);for(ll i=n;i<=m;i++){solve(i);}return 0;}