線型素數篩+質因素分解+組合數。
AC后發現這樣做效率有點低。。766ms。
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<time.h> #include<iostream> #include<algorithm> #include<cmath> using namespace std;typedef long long LL; int tol; LL factor[100]; const int N = 2000001; LL prime[N] = {0},num_prime = 0; int isNotPrime[N] = {1, 1};void findfac(long long n) {for(int i=0; i<num_prime; i++){if(n%prime[i]!=0) continue;while(1){if(n==1||n%prime[i]!=0) break;factor[tol++]=prime[i];n=n/prime[i];}if(n==1) break;} }int num[100],tot; long long c[25][25];void init() {c[1][1]=1;for(int i=1; i<=20; i++) c[i][0]=1;for(int i=2; i<=20; i++){for(int j=1; j<=20; j++){c[i][j]=c[i-1][j-1]+c[i-1][j];}}for(long i = 2 ; i < N ; i ++){if(! isNotPrime[i])prime[num_prime ++]=i;for(long j = 0 ; j < num_prime && i * prime[j] < N ; j ++){isNotPrime[i * prime[j]] = 1;if( !(i % prime[j] ) ) break;}} }int main() {init();long long n;while(~scanf("%lld",&n)){if(n==1) {printf("%d %lld\n",1,1);continue;}tol=0;findfac(n);sort(factor,factor+tol);tot=0,num[tot]=1;for(int i=1;i<tol;i++){if(factor[i]==factor[i-1]) num[tot]++;else{tot++;num[tot]=1;}}tot++;int sum=tol;int ans1=tol;long long ans2=1;for(int i=0;i<tot;i++){ans2=ans2*c[sum][num[i]];sum=sum-num[i];}printf("%d %lld\n",ans1,ans2);}return 0; }
?