글 읽기 - 반례를 찾아주세요..!

jbs30_jsh 2년 전 0

자꾸 96%에서 틀립니다..ㅜㅜ

제곱수로 나누어지면 무한개이고

아니면 소인수를 배열하는 경우의 수니까 (소인수 개수)! 를 출력하도록 설계했습니다.

#include<stdio.h>
#include<stdlib.h>
typedef long long int lo;
lo s[40000];
lo fpow(lo n,lo k,lo p){ //빠른 거듭제곱 
	lo s=1;
	for(;k;k>>=1){
		if(p){
			if(k&1) s=(__int128)s*n%p;
			n=(__int128)n*n%p;
		}
		else{
			if(k&1) s=(__int128)s*n;
			n=(__int128)n*n;
		}
	}
	return s;
}

lo miller(lo n,lo a){ //밀러 라빈 소수 판정 
	lo t=n-1;
	while(t%2==0) if(fpow(a,t/=2,n)==n-1) return 1;
	t=fpow(a,t,n);
	return t==n-1 || t==1;
}
lo prime(lo n){ //소수 판정 
	if(n==1) return 0;
	int m=12,i;
	lo a[12]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
	for(i=0;i<m;i++){
		if(a[i]==n) return 1;
		if(!miller(n,a[i])) return 0;
	}
	return 1;
}
lo gcd(lo a,lo b){ //최대공약수 
	return b?gcd(b,a%b):a;
}
lo rf(lo x,lo n){ //폴라드 로에서 쓸 신기한 값 
	return ((__int128)x*x+13)%n;
}
lo pollard_rho(lo n){ //폴라드 로 알고리즘 
	lo x=2,y=2,t=1,c=13;
	if(prime(n)) return n;
	if(n%2==0) return 2;
	while(t==1 || t==n){
		x=rf(x,n);
		y=rf(rf(y,n),n);
		t=gcd(x>y?x-y:y-x,n);
		if(t==n) x=y=rand()%n;
	}
	return prime(t)? t:pollard_rho(t);
}
lo factorize(lo n){ //소인수분해 
	lo r,i,j,p=0;
	while(n-1){
		r=pollard_rho(n);
		n/=r;
		s[p++]=r;
	}
	for(i=0;i<p;i++){ //버블 정렬 
		for(j=0;j<p-i-1;j++){
			if(s[j]>s[j+1]){
				lo t=s[j];
				s[j]=s[j+1];
				s[j+1]=t;
			}
		}
	}
	return p;
}
lo fac(lo k){ //k!
	lo i,s=1;
	for(i=2;i<=k;i++){
		s=(__int128)s*i;
	}
	return s;
}
int main(){
	int t,i;
	lo j,n;
	scanf("%d",&t);
	for(i=0;i<t;i++){
		lo prv=0,ans=0,p=0;
		scanf("%lld",&n);
		p=factorize(n); //인수분해(소인수의 개수 리턴) 
		
		prv=s[0];
		for(j=1;j<p;j++){
			if(prv==s[j]){ //이전과 똑같은 인수 있으면 무한개 
				ans=-1;
				break;
			}
			else{
				prv=s[j];
			}
		}
		
		if(!ans){
			ans=fac(p); //p!
		}
		
		for(j=0;j<p;j++) s[j]=0;
		printf("%lld\n",ans);
	}
}