আলোচনাঃ
আমাকে একটা range(low থেকে high) দেয়া থাকবে । সেই range এর মধ্যে K ( K always odd ) সংখ্যক divisor আছে এমন কয়টা সংখ্যা পাওয়া যায় তা বের করা লাগবে। যেমনঃ 2 থেকে 49 এর মধ্যে 4টা নম্বর আছে যাদের divisor = 3 .
উত্তরঃ
প্রশ্নে একটা কথা বলা আছে যে, K odd integer . তাহলে odd সংখ্যক divisor কাদের থাকবে সেটা আগে বুঝতে হবে।
| number | divisor | Total divisor |
| 1 | 1 | 1 |
| 2 | 1, 2 | 2 |
| 4 | 1,2,4 | 3 |
| 6 | 1,2,3,4 | 4 |
| 9 | 1,3,9 | 3 |
| 25 | 1,5,25 | 3 |
| 36 | 1,2,3,4,6,9,12,18,36 or,Prime factorization = 2^2 * 3^2 = (2+1)*(2+1) | 9 |
| 49 | 1,7,49 | 3 |
তাহলে দেখা যাচ্ছে , পূর্ণবর্গ সংখ্যাগুলোর divisor count always odd হচ্ছে।
তাহলে মনে আসতেই পারে যে, পূর্ণবর্গ সংখ্যাগুলোর divisor count বের করলেই হবে। কিন্তু এটা করলে একটা range এর মধ্যে K সংখ্যক divisor আছে এমন কয়টা সংখ্যা আছে তা কি করে বুঝব?
এর জন্য আমরা একটা কাজ করতে পারি আর তা হলো , কোনো একটা নির্দিষ্ট divisor এর কতগুলো সংখ্যা আছে তা হিসাব করে রাখতে পারি।
মানে হচ্ছে আমার divisor সংখ্যা যদি 3 হয় তাহলে divisor সংখ্যা 3 এমন নম্বর(4,9,24,49………….) কে আমি কোথাও একটা store করে রাখবো। তাহলে সুবিধাটা কি?
এটা করলে আমরা একটা নির্দিষ্ট range এর মধ্যে K সংখ্যক divisor আছে এমন কয়টা সংখ্যা আছে তা খুব সহজেই upper bound আর lower bound এর বিয়োগফল দিয়ে বের করে ফেলতে পারবো। কারণ কোনো একটা range এর মধ্যে কয়টা সংখ্যা আছে তা আমরা এভাবে বের করতে পারি।
এটা বুঝার জন্য (https://vjudge.net/problem/LightOJ-1088 ) এই প্রবলেমটা Solve করতে পারো।
এখন c=10^5 and 0<=low,high<=10^10 যা অনেক বড়। এখন যদি normal way তে
পূর্ণবর্গ সংখ্যার divisor count বের করতে চাই তাহলে TLE খাবো। কারণ 10^10 পর্যন্ত loop চালানো সম্ভব না। তাহলে কি করা যায়?
আমরা আসলে 25 এর divisor count বের না করে 5 এর divisor count থেকেই 25 এর
divisor count বের করতে পারি। কিভাবে?
আমরা জানি, 5 এর prime factorization =5^1
so, 5 এ divisor আছে = (1+1) = (a+1) = 2 [so, here a=1]
তাহলে, 25 এ divisor থাকবে = ((2a)+1) টা = (2*1)+1 টা= 3 টা
তাহলে দেখতে পাচ্ছি যে, 25 এর divisor বের না করে এর sqrt(25)=5 থেকেই আমরা 25 এর divisor count বের করতে পারি।
আবার, 24=2^3 +3^1 . So, (24)^2 = (2*a1+1)*(2*a2+1) = (2*3+1)*(2*1+1) =21.So, number of divisors for 24 is 21 .
আর low,high এর highest value যেহেতু 10^10, তাহলে এর sqrt(10^10)=10^5 হবে
যার divisor count আমরা সহজেই বের করতে পারি ।prime factorization দিয়ে divisor count করার জন্য sieve দিয়ে prime number গুলো আগেই generate করে রাখতে পারি।
C++ Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5;
const ll mxN=2e3;
vector<ll> prime,factor[N];
bool vis[N];
void divCount(ll n){ // O(sqrt(n))
ll temp=n;
ll ans=1;
for(ll i=0;i<prime.size() && prime[i]*prime[i]<=n;i++){
ll cn=0;
if(n%prime[i]==0){
while(n%prime[i]==0){
cn++;
n/=prime[i];
}
ans=ans*(2*cn+1); // formula and here, cn = a
}
}
if(n>1){
ans=ans*3; // here, if n>1 then we should multiply ans by 3
}
// divisor =3 ,then temp = 2, 3 , 5, 7......
// so, temp*temp = 4, 9, 25, 49..........
factor[ans].push_back(temp*temp); // factor[3].push_back(2*2,3*3,5*5...)
}
void sieve(){
for(ll i=3;i*i<=N;i+=2){
if(vis[i]==0){
for(ll j=i*i;j<=N;j+=2*i){
vis[j]=1;
}
}
}
prime.push_back(2);
for(ll i=3;i<=N;i+=2){
if(vis[i]==0) prime.push_back(i);
}
}
int main(){
sieve(); //O(Nlog(logN))
for(ll i=1;i<=N;i++){
divCount(i);
}
ll t,k,l,r;
scanf("%lld",&t);
while(t--){
scanf("%lld%lld%lld",&k,&l,&r);
auto LB=lower_bound(factor[k].begin(),factor[k].end(),l)-factor[k].begin(); //O(logN)
auto UB=upper_bound(factor[k].begin(),factor[k].end(),r)-factor[k].begin(); //O(logN)
printf("%lld\n",UB-LB);
}
}