ในปัญหานี้ เราได้รับค่าจำนวนเต็มสามค่า 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 เราจะบวก 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
