AIME 1995 · 第 6 题

Solution 1

We know that $n^2 = 2^{62}3^{38}$ must have $(62+1)\times (38+1)$ factors by its prime factorization. If we group all of these factors (excluding $n$) into pairs that multiply to $n^2$, then one factor per pair is less than $n$, and so there are $\frac{63\times 39-1}{2} = 1228$ factors of $n^2$ that are less than $n$. There are $32\times20-1 = 639$ factors of $n$, which clearly are less than $n$, but are still factors of $n$. Therefore, using complementary counting, there are $1228-639=\boxed{589}$ factors of $n^2$ that do not divide $n$.

Solution 2

Let $n=p_1^{k_1}p_2^{k_2}$ for some primes $p_1,p_2$. Then $n^2$ has $\frac{(2k_1+1)(2k_2+1)-1}{2}$ factors less than $n$.

This simplifies to $\frac{4k_1k_2+2k_1+2k_2}{2}=2k_1k_2+k_1+k_2$.

The number of factors of $n$ less than $n$ is equal to $(k_1+1)(k_2+1)-1=k_1k_2+k_1+k_2$.

Thus, our general formula for $n=p_1^{k_1}p_2^{k_2}$ is

Number of factors that satisfy the above $=(2k_1k_2+k_1+k_2)-(k_1k_2+k_1+k_2)=k_1k_2$

Incorporating this into our problem gives $19\times31=\boxed{589}$.

Solution 3

Consider divisors of $n^2: a,b$ such that $ab=n^2$. WLOG, let $b\ge{a}$ and $b=\frac{n}{a}$

Then, it is easy to see that $a$ will always be less than $b$ as we go down the divisor list of $n^2$ until we hit $n$.

Therefore, the median divisor of $n^2$ is $n$.

Then, there are $(63)(39)=2457$ divisors of $n^2$. Exactly $\frac{2457-1}{2}=1228$ of these divisors are $

There are $(32)(20)-1=639$ divisors of $n$ that are $.

Therefore, the answer is $1228-639=\boxed{589}$.

Video Solution by OmegaLearn

https://youtu.be/jgyyGeEKhwk?t=259

~ pi_is_3.14