Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

n이 되도록 x의 최대값을 구하세요! C++에서 %(k^x) =0

<시간/>

두 개의 정수 n과 k가 있다고 가정합니다. n!이 되도록 x의 최대값을 찾아야 합니다. mod (k^x) =0. 따라서 n =5이고 k =2일 때 출력은 3이 됩니다. As n! =120, 이제 x의 다른 값에 대해 -

120 mod 2^0 =0, 120 mod 2^1 =0, 120 mod 2^2 =0, 120 mod 2^3 =0, 120 mod 2^4 =8, 120 mod 2^5 =24, 120 mod 2^6 =56, 120 mod 2^7 =120. x =3의 최대값이므로 결과는 0이므로 출력은 3입니다.

이 문제를 해결하려면 다음 단계를 따라야 합니다.

  • k의 제곱근을 취해 m에 저장합니다.
  • i :=2 ~ m의 경우 다음 단계를 수행하십시오.
    • i =m일 때 i :=k로 설정
    • k가 i로 나누어지면 k를 i로 나눕니다.
    • n에 루프를 실행하고 u라는 변수에 몫을 추가합니다.
    • 각 루프 후에 r의 최소값 저장

#include <iostream>
#include <cmath>
using namespace std;
int calculateMaxX(int n, int k) {
   int result = n, v, u;
   int m = sqrt(k) + 1;
   for (int i = 2; i <= m && k > 1; i++) {
      if (i == m) {
         i = k;
      }
      for (u = v = 0; k % i == 0; v++) {
         k /= i;
      }
      if (v > 0) {
         int t = n;
         while (t > 0) {
            t /= i;
            u += t;
         }
         result = min(result, u / v);
      }
   }
   return result;
}
int main() {
   int n = 5;
   int k = 2;
   cout<<"Maximum value of x is: " << calculateMaxX(n, k);
}

출력

Maximum value of x is: 3