题目链接： 点我 题目大意： 给出一个X，求一个1……X的最长递增数列，要求相邻两个可以整除，在求出有多少个这样的数列。比如给出6。1,2,6（这是最长）1,3,6（这是第二种). 题目解析： X分解质因数的个数就是最长的数列，再把质因数排列组合一下就好了。 PS：输出longlong型的要用“%lld”，WA了半天。。。
Problem: 3421 User: ChenyangDu Memory: 4944K Time: 422MS Language: C++ Result: Accepted Source Code #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int maxn = 1<<20; int n,length,primes,is_prime[maxn]; vector <int> prime_c; struct num{int id,times;}; num Num(int id,int times){ num t; t.id = id; t.times = times; return t; } long long A(int a){ long long ans = 1; for(int i=1;i<=a;i++){ ans *= i; } return ans; } void get_prime(){ memset(is_prime,-1,sizeof(is_prime)); for(int i=2;i<(maxn);i++){ if(is_prime[i]){ for(int j=i;j<(maxn);j+=i){ is_prime[j] = false; } prime_c.push_back(i); } } } int main(){ //freopen("in.txt","r",stdin); get_prime(); while(scanf("%d",&n) == 1){ length = primes = 0; vector <num> prime; for(int j=0;j<prime_c.size();){ int i = prime_c[j]; if(i>n)break; if(n%i == 0){ primes++; if(prime.empty() || prime.back().id != i){ prime.push_back(Num(i,1)); }else { prime.back().times++; } n /= i; }else j++; } long long ans = A(primes); for(int i=0;i<prime.size();i++){ ans /= A(prime[i].times); } printf("%d %lld\n",primes,ans); } return 0; }