本题的大意是，给定一个数x，求出一个以1开头，x为结尾，中间的每一项大于前一项而且是前一项的倍数，求这样一个序列的最长长度和在最长长度情况下有多少种组合情况。
一开始想了想没什么想法……暴搜？可能T掉。后来发现，为了保证最长的话，肯定每次乘的数都是一个质数，否则如果是一个合数的话，我们可以把它拆分成多个质数继续乘，肯定比原来要长。然后又发现，这个序列中的每一项必然是X的一个因子，那么每次乘的质数也必然是x的因子。
想到了什么？唯一分解定理！那问题就很显然了，我们把X进行唯一分解，得到的质因数个数就是序列最长长度（k）。然后如果不考虑重复的话，那么有k！种情况，不过因为一个质因数会出现多次，所以每出现一个重复的质因数（出现次数为p），我们要把答案除以p！。这个好像直接算阶乘会爆longlong，所以我选择的方法是分解因数，然后开一个桶来计算。
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<vector> #include<queue> #define pb push_back #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 40005; const int N = 2000005; const int INF = 1000000009; const ll mod = 51123987; ll read() { ll ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } int x,pri[N],times[M],p[N],tot,cur,bucket[M],cnt,ans; bool np[N]; void euler() { int k = 2000000; np[1] = 1; rep(i,2,k) { if(!np[i]) p[++tot] = i; for(int j = 1;i * p[j] <= k;j++) { np[i * p[j]] = 1; if(!(i % p[j])) break; } } } void clear() { memset(times,0,sizeof(times)); memset(bucket,0,sizeof(bucket)); } void div(int x) { cur = 0,cnt = 0; rep(i,1,tot) { if(!(x%p[i])) pri[++cur] = p[i]; while(!(x % p[i])) x /= p[i],times[cur]++,cnt++; if(x == 1) break; } } void calc() { ans = 1; rep(i,2,cnt) { int p = i; rep(j,2,cnt) { while(p % j == 0) p /= j,bucket[j]++; if(p == 1) break; } } //rep(i,1,cur) printf("%d ",times[i]);enter; //rep(i,1,cnt) printf("%d ",bucket[i]);enter; rep(i,1,cur) { if(times[i] > 1) { rep(k,2,times[i]) { int p = k; rep(j,2,cnt) { while(p % j == 0) p /= j,bucket[j]--; if(p == 1) break; } } } } //rep(i,1,cnt) printf("%d ",bucket[i]);enter; rep(i,1,cnt) while(bucket[i]) ans *= i,bucket[i]--; printf("%d %d ",cnt,ans); } int main() { euler(); while(scanf("%d",&x) != EOF) clear(),div(x),calc(); return 0; }