446. Smooth Divisors

A positive integer m is called a smooth divisor of a number n if, when dividing n by m, the quotient and remainder are the same. For a given positive integer n, find the number of its smooth divisors.

Input. One positive integer n (1 ≤ n ≤ 10⁶).

Output. Print a single number – the number of smooth divisors of n.

Sample input	Sample output
20	2

SOLUTION

loops

Algorithm analysis

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 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 ≤ m ≤ 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 ≤ m ≤ n) for which the quotient of n divided by m is equal to the remainder of n divided by m.