이 문제에서는 세 개의 정수 값 L, R 및 k가 제공됩니다. 우리의 임무는 주어진 범위에서 K개의 홀수 제수가 있는 숫자를 찾는 것입니다. [L, R] 범위에서 정확히 k개의 제수가 있는 숫자의 개수를 찾습니다.
1과 숫자 자체를 제수로 계산합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
a = 3, b = 10, k = 3
출력
2
설명
Numbers with exactly 3 divisors within the range 3 to 10 are 4 : divisors = 1, 2, 4 9 : divisors = 1, 3, 9
솔루션 접근 방식
문제에 대한 간단한 해결책은 k 제수를 계산하는 것입니다. 따라서 k가 홀수(문제에 표시된 대로)가 되려면 숫자가 완전제곱수여야 합니다. 따라서 완전제곱수에 대한 제수 수만 계산합니다(이렇게 하면 컴파일 시간이 절약됨). 그리고 k의 제수의 개수가 있으면 numbercount에 1을 더합니다.
우리 솔루션의 작동을 설명하는 프로그램
예시
#include<bits/stdc++.h>
using namespace std;
bool isPerfectSquare(int n) {
int s = sqrt(n);
return (s*s == n);
}
int countDivisors(int n) {
int divisors = 0;
for (int i=1; i<=sqrt(n)+1; i++) {
if (n%i==0) {
divisors++;
if (n/i != i)
divisors ++;
}
}
return divisors;
}
int countNumberKDivisors(int a,int b,int k) {
int numberCount = 0;
for (int i=a; i<=b; i++) {
if (isPerfectSquare(i))
if (countDivisors(i) == k)
numberCount++;
}
return numberCount;
}
int main() {
int a = 3, b = 10, k = 3;
cout<<"The count of numbers with K odd divisors is "<<countNumberKDivisors(a, b, k);
return 0;
} 출력
The count of numbers with K odd divisors is 2