We need to find the number of numbers in a given interval with k (an odd number) of divisors.
The number of divisors is k which is an odd number. Only perfect squares have odd number of divisors.
So once we are given an interval say [low, high] - all we need to do is to see how many perfect squares in this interval have k divisors.
sqrt(high) will give the last perfect square in this interval but sqrt(low) might not be the first perfect square in this interval.
k = sqrt(low)
if(k*k<low)
k++;
k now is the smallest perfect square in the interval.
int divisors(int x)
{
int y = sqrt(x);
int count = 0;
for(int i = 1; i<=y; i++)
{
if(x%i==0)
count = count + 2; //this is because both i and x/i are divisors of x
}
if(y*y==x)
count = count - 1; //this is because we are counting y twice. here i will be x/i.
return count;
}
We can use the above function and iterate over the perfect squares in the interval to check how many of them have k divisors.
This method of counting divisors takes
time for input number
. The worst case for the interval
![$[1, 10^{10}]$](//latex.artofproblemsolving.com/1/b/e/1bec8a4785b6e4ec87cea403806bd860ed89027f.png)
will take
too much time and the time limit will be exceeded.
There are
number of perfect squares less or equal to
.Can we relate the number of factors of
to the number of factors of
?
Let
where all
are prime numbers.
Then
will have
number of divisors.
We think in terms of sieve of Eratosthenes to find the smallest prime number that divides a given number x.
This link gives a method to do so:
http://codeforces.com/blog/entry/7262
Once this is done, the number of divisors of a number x is easy to find.
sp[x] stores the smallest prime factor of x as in the link above.
int divi,prod,count,j;
int ans[100005];
for(int i = 1; i<=100000; i++)
{
prod = 1;
count = 0;
j = i;
while(j>1)
{
divi = sp[j];
while(j%divi==0)
{
count++;
j = j/divi;
}
prod = prod*(2*count+1);
count = 0; //reset count to 0 for the next prime factor
}
ans
= prod; //ans stores the number of divisors of i*i
}
Well now that we have precomputed and stored the number of divisors of every perfect square from
to
, we can simply
iterator over our interval and see which perfect squares have k number of divisors.
This should work, shouldn't it? It will give Time Limit Exceeded again. Why this time?
Too many test cases.
How do we tackle this?
We can store the numbers for every k possible. We use an array of vectors:
vector<int> a[10001];
Now a[k] will be a vector where we push_back every square root of every number which has k divisors. We add one statement in our last snippet:
ans
= prod; //ans stores the number of divisors of i*i
a[prod].push_back(i); //i*i has prod number of divisors.
//lowps*lowps is the smallest perfect square in the given interval
//upps*upps is the largest perfect square in the given interval
//k is the number of divisors we are looking for
//note that binary search on a[k] is possible because it is sorted
int find(long long lowps, long long upps, long long k)
{
vector<int>::iterator itl,itr;
itl = lower_bound(a[k].begin(), a[k].end(), lowps);//first number in a[k] not less than lowps
itr = upper_bound(a[k].begin(), a[k].end(), upps);//first number in a[k] greater than upps
if(itl == a[k].end()) //this is so when every number in the list is less than lowps
return 0;
itr--;
return (itr - itl + 1);
}
//to know about lower_bound in detail:
http://www.cplusplus.com/reference/algorithm/lower_bound/
//to know about upper_bound in detail:
http://www.cplusplus.com/reference/algorithm/upper_bound/
We use slight variants of binary search to find the answer quickly. Now the number of test cases in the problem shouldn't be a problem.
by StarLex1, Apr 15, 2025, 7:58 AM ![$f:[0,1]\rightarrow\mathbb{R}$](http://latex.artofproblemsolving.com/9/d/0/9d00bb0f11e69022dded4a8baba1b496f66d272e.png)
,is a convex function and 
![\[\left(\int^{1}_{0}f(x)dx\right)^2\leq \dfrac{3}{4}\int^1_{0}f^2(x)dx\]](http://latex.artofproblemsolving.com/a/a/0/aa0ae3023a71f3452170023452601cc7df785eb9.png)
and 
be two points that are diametrically opposite to each other on a unit sphere. 
right square pyramids are fitted along the line segment 
, such that the apex and altitude of each pyramid 
, where 
, are 
and 
respectively, and the points 
are collinear.
and 
invertible. Prove that if 
for any positive integer 
then 
be a function which is continuous on ![\( [0,1] \)](http://latex.artofproblemsolving.com/0/1/0/01026be294289be8f090c7b2586dde64a0d5b479.png)
and differentiable on 
, with 
. Assume that there is some 
such that 
. Prove that there exists some 
such that 
.
given by 
and 
, for all 
. Show that 
Mathematical Gazette
be a real-valued function that is twice continuously differentiable throughout 
, and define![\[
\rho (x,y)=yh_x -xh_y .
\]](http://latex.artofproblemsolving.com/7/3/6/736993597c4b45cf77b9013185d2a4d931a7d231.png)
Prove or disprove: For any positive constants 
and 
with 
, there is a circle 
of radius 
over the interior of 
in the worst case.
and, for 
![\[a_n=\dfrac{6a_{n-1}^2a_{n-3}-8a_{n-1}a_{n-2}^2}{a_{n-2}a_{n-3}}.\]](http://latex.artofproblemsolving.com/b/c/6/bc6686c63a96c3be5575542d7ac120c2fa7e69b2.png)
Show that, for all 
is an integer multiple of 
be a polynomial of degree 
we have 
. When does equality occur?
June 2016
time for input number ![$[1, 10^{10}]$](http://latex.artofproblemsolving.com/1/b/e/1bec8a4785b6e4ec87cea403806bd860ed89027f.png)
will take
number of perfect squares less or equal to 
.
?
where all 
are prime numbers.
number of divisors.
to 
November 2016