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 의 총 개수.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 4857: 탈출 [토폴로지]1 번 부터 n 번 까지 입 니 다.동시에 일부 이상 한 제약 조건 이 있 는데 모두 a 는 b 전에 있어 야 한다. 이 사람들 은 가난 한 사람 도 있 고 부자 도 있다.1 번 이 가장 부유 하고 2 번 이 두 번...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.