NYOJ 56 단계 곱 하기 인수 분해 (1)

2676 단어 활용 단어 참조
주소
 1 #include<stdio.h>
 2 int main()
 3 {
 4     int i,j,k,m,n,s;
 5     scanf("%d",&s);
 6     while(s--)
 7     {
 8         scanf("%d%d",&n,&m);
 9         for(i=m,j=0;i<=n;i++)
10         for(k=i;!(k%m);j++)
11         k=k/m;
12         printf("%d
",j); 13 } 14 return 0; 15 }

생각:
주어진 두 개의 수 m, n
제발분해 질량 인수 후 인자 n 의 개수.
이 문 제 는 대수 문제 와 관련 되 어 있 으 며, 곱 하기 직접 구하 면 데이터 형식의 범 위 를 넘 어 설 수 있다.
다음은 효율 이 비교적 높 은 알고리즘 을 제시 합 니 다. 우 리 는 한 걸음 한 걸음 합 시다.
m!=1*2*3*……*(m-2)*(m-1)*m
n 배수 와 관련 된 모든 곱 하기 와 n 을 곱 하 는 것 은 관계 가 없다 는 것 을 나 타 낼 수 있다.
    =(n*2n*3n*......*kn)*ohter     other 는 n 인자 가 없 는 수의 곱 이다.   왜냐하면 k 가 최대 치 일 거 예요.  그래서 k = m / n
    =n^k*(1*2*......*k)*other  
    =n^k*k!*other     
이 표현 식 에서 k 개 n 을 추출 한 다음 같은 방법 으로 순환 하면 k 를 구 할 수 있 습 니 다!중인 자 n 의 개수.
매번 n 의 개 수 를 구 하 는 합 은 m!중인 자 n 의 총 개수.

좋은 웹페이지 즐겨찾기