poj1741，POJ 3421 X-factor Chains

2023-11-19 阅读 23 评论 0

摘要：線型素數篩+質因素分解+組合數。 AC后發現這樣做效率有點低。。766ms。 #include<stdio.h> #include<string.h> #include<stdlib.h> #include<time.h> #include<iostream> #include<algorithm> #include<cmath> using name

線型素數篩+質因素分解+組合數。

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;
}