Smooth Divisors (Editorial)

Since the value of $n$ is not too large, we can iterate through all possible values of $m$ from $2$ to $n$ and check if the condition \lfloor n / m \rfloor = n~mod~m holds. Count the number of such $m$.

Example

For n = 20 there are two smooth divisors: $9$ and $19$, because

• 20~/~9 = 20~mod~9 = 2;

• 20~/~19 = 20~mod~19 = 1

Algorithm implementation

Read the input value of $n$.

scanf("%d",&n);

In the variable $res$, count the number of such values of m~(2 \le m \le n) for which the quotient of $n$ divided by $m$ is equal to the remainder of $n$ divided by $m$.

res = 0;
for(m = 2; m <= n; m++)
  if ((n / m) == (n % m)) res++;

Print the answer.

printf("%d\n",res);	

Java implementation

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int res = 0;
    for(int m = 2; m <= n; m++)
      if ((n / m) == (n % m)) res++;
    System.out.println(res);
    con.close();
  }
}

Python implementation

Read the input value of $n$.

n = int(input())

In the variable $res$, count the number of such values of m~(2 \le m \le n) for which the quotient of $n$ divided by $m$ is equal to the remainder of $n$ divided by $m$.

res = 0
for m in range(2,n) :
  if (n // m == n % m) : res += 1

Print the answer.

print(res)