一开始没读懂题意,不太明白 Xi | Xi+1 where a | b means a perfectly divides into b的意思,后来才发现是要满足后一个数是前一个数的倍数
题目要求1 = X0, X1, X2, …, Xm = X,并且后一个数是前一个数的倍数,为了得到最长链,必须将数X进行质因数分解,
假设X=(a[1]^b[1])*...*(a[i]^b[i])*..(a[n]^b[n]),设m=b[1]+b[2]+..b[i]+b[n];
a[i]为X的质因数,b[i]为X的质因数为a[i]的个数,m为总的质因数的个数(质因数不包含1,1不是质数)
接下来就是一个排列组合问题了,注意m为总的质因数的个数
为了得到最长链,由于最后一位为m个质因数相乘,则前一位可以任取m-1个质因数相乘,再前一位可选m-2个质因数相乘,以此类推,第一位X1(非X
0)可任取1个质因数.
由此可知最长链的长度为m(m为总的质因数的个数)(因为任意一个质因数都不能再分解);
设fact(n)为n的阶乘
则最长链的个数=fact(m)/fact(a[1])/fact(a[2]).../fact(a[i])/../fact(a[n]);
一开始交了两次都TLE了,后来直接在质因数分解里面计算阶乘就A了.
TLE代码:
/* * Created: 2016年03月30日 10时34分42秒 星期三 * Author: Akrusher * */ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <deque> #include <list> #include <set> #include <map> #include <stack> #include <queue> #include <numeric> #include <iomanip> #include <bitset> #include <sstream> #include <fstream> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define in(n) scanf("%d",&(n)) #define in2(x1,x2) scanf("%d%d",&(x1),&(x2)) #define inll(n) scanf("%I64d",&(n)) #define inll2(x1,x2) scanf("%I64d%I64d",&(x1),&(x2)) #define inlld(n) scanf("%lld",&(n)) #define inlld2(x1,x2) scanf("%lld%lld",&(x1),&(x2)) #define inf(n) scanf("%f",&(n)) #define inf2(x1,x2) scanf("%f%f",&(x1),&(x2)) #define inlf(n) scanf("%lf",&(n)) #define inlf2(x1,x2) scanf("%lf%lf",&(x1),&(x2)) #define inc(str) scanf("%c",&(str)) #define ins(str) scanf("%s",(str)) #define out(x) printf("%d ",(x)) #define out2(x1,x2) printf("%d %d ",(x1),(x2)) #define outf(x) printf("%f ",(x)) #define outlf(x) printf("%lf ",(x)) #define outlf2(x1,x2) printf("%lf %lf ",(x1),(x2)); #define outll(x) printf("%I64d ",(x)) #define outlld(x) printf("%lld ",(x)) #define outc(str) printf("%c ",(str)) #define pb push_back #define mp make_pair #define fi first #define se second #define SZ(x) ((int)(x).size()) #define mem(X,Y) memset(X,Y,sizeof(X)); typedef vector<int> vec; typedef long long ll; typedef pair<int,int> P; const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; const int INF=0x3f3f3f3f; const ll mod=1e9+7; ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} const bool AC=true; ll all,temp,num; map <int,int> p; ll fact(int n){ ll res=1; for(ll i=2;i<=ll(n);i++){ res*=i; } return res; } map<int,int> factor; map<int,int> prime_factor(int n){ map<int,int> res; for(int i=2;i*i<=n;i++){ while(n%i==0){ ++res[i]; n/=i; } } if(n!=1){ res[n]=1; // } return res; } int main() { int n; while(in(n)==1){ all=1;temp=1;num=0; p=prime_factor(n); for(int i=2;i<=n;i++){ //本身可能也是质因数 if(p[i]!=0){ num+=p[i]; temp*=fact(p[i]); } } all=fact(num); printf("%lld %lld",num,all/temp); } return 0; }
以下为AC代码
/* * Created: 2016年03月30日 10时34分42秒 星期三 * Author: Akrusher * */ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <deque> #include <list> #include <set> #include <map> #include <stack> #include <queue> #include <numeric> #include <iomanip> #include <bitset> #include <sstream> #include <fstream> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define in(n) scanf("%d",&(n)) #define in2(x1,x2) scanf("%d%d",&(x1),&(x2)) #define inll(n) scanf("%I64d",&(n)) #define inll2(x1,x2) scanf("%I64d%I64d",&(x1),&(x2)) #define inlld(n) scanf("%lld",&(n)) #define inlld2(x1,x2) scanf("%lld%lld",&(x1),&(x2)) #define inf(n) scanf("%f",&(n)) #define inf2(x1,x2) scanf("%f%f",&(x1),&(x2)) #define inlf(n) scanf("%lf",&(n)) #define inlf2(x1,x2) scanf("%lf%lf",&(x1),&(x2)) #define inc(str) scanf("%c",&(str)) #define ins(str) scanf("%s",(str)) #define out(x) printf("%d ",(x)) #define out2(x1,x2) printf("%d %d ",(x1),(x2)) #define outf(x) printf("%f ",(x)) #define outlf(x) printf("%lf ",(x)) #define outlf2(x1,x2) printf("%lf %lf ",(x1),(x2)); #define outll(x) printf("%I64d ",(x)) #define outlld(x) printf("%lld ",(x)) #define outc(str) printf("%c ",(str)) #define pb push_back #define mp make_pair #define fi first #define se second #define SZ(x) ((int)(x).size()) #define mem(X,Y) memset(X,Y,sizeof(X)); typedef vector<int> vec; typedef long long ll; typedef pair<int,int> P; const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; const int INF=0x3f3f3f3f; const ll mod=1e9+7; ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} const bool AC=true; ll all,temp,num; int n; map <int,int> p; ll fact(int b){ //计算阶乘 ll res=1; for(ll i=2;i<=ll(b);i++){ res*=i; } return res; } void prime_factor(int n){ //质因数分解 map<int,int> res; for(int i=2;i*i<=n;i++){ while(n%i==0){ ++res[i]; n/=i; all++; //all是所有质因数的个数 temp*=res[i];//计算重复的组数(在外面计算会超时) } } if(n!=1){ //能分解得到的最大质因数 res[n]=1; all++; } } int main() { while(in(n)==1){ all=0;temp=1;num=0;//注意初始化 prime_factor(n); num=all;//保存最长链的长度 all=fact(num);//计算总的阶乘 printf("%lld %lld ",num,all/temp); } return 0; }