Counting Factor Trees zoj 3405
Time Limit: 2 Seconds
Memory Limit: 65536 KB
Factoring, i.e., listing all the prime factors, of an integer is a useful skill that often helps to solve math problems. For example, one of the ways to find the GCD (Greatest Common Divisor) or LCM (Least Common Multiple) of two integers is by listing all their prime factors. The GCD is then the product of all the common factors; the LCM is the product of all the remaining ones.
The Factor Tree is a tool for finding such prime factorizations. The figure below demonstrates three factor trees of 108. At the beginning a root with a number is given, say N, which is to be factored. Then, the root is factored into two children N1 and N2 such that N = N1 × N2 (N1 ≥ 2, N2 ≥ 2). Note that N1 and N2 need not be prime. The same factoring process continues until all the leaves are prime.
While the prime factorization is unique, the factor tree reflects the order in which the factors were found, and is by no means unique. So, how many factor trees of a number are there?
Input
There are no more than 10000 cases. A line containing an integer N (2 ≤ N ≤ 1000000000) is given for each case.
Output
Print the number of factor trees of N in a line for each case. The answer will be fit in a signed 64-bit integer.
Sample Input
12
108
642485760
Sample Output
6
140
9637611984000
Author: GAO, YuanContest: ZOJ Monthly, September 2010
비극적이다!시합 때 못해서 시합 후에 CE, TLE가 지나면 그만이고 플로팅 포인트 Error도 왔어요.
TLE의 Method 함수에 주의하십시오. 즉, x개의 요소가 얼마나 많은 배열 방법을 가진 함수를 구하는 것입니다.
원래 썼어요.
int Method(int num)
{
if(a[num])
return a[num];
int i,j;
int temp=0;
for(i=1;i<=num/2;i++)
{
temp+=Method(i)*Method(num-i)*2;
}
if(num%2==0)
temp-=Method(num/2)*Method(num/2);
return temp;
}
= =!
이렇게 temp-=Method(num/2)*Method(num/2);다시 계산해야 되는 거 아니야!!
#include
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
B God Create Math 사고방식B.God Create Math There is a saying: computer was the crystallizationof men' intelligence, but math is fromgod. Today, ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.