Let's sell Jeongjeheon!
Time limit5sMemory limit128 MB
For each input line giving 1/n, count the unordered positive integer pairs x and y with 1/x + 1/y = 1/n.
- Level
Medium4 of 10
- Topics
- Number theory, Math
- Solved
- No attempts yet
Problem
In the Anam valley there is a well known pharmaceutical company called ALPS (Anam Lotated Pill Station). It is famous because every drug it makes uses only two ingredients, soju and beer. Jaeheon, the president of ALPS, sells his drugs believing that the right mixture of soju and beer cures any illness.
At the start of the new year, after a heavy round of his own medicine, Jaeheon gave the company these resolutions.
- Every flask and beaker used in the company must have a capacity of the form , where is a positive integer.
- Every drug, whether it is for sale or for storage, must fill its flask or beaker completely.
- Three times a week, shout the company name toward the east.
The staff had been drinking the same medicine, so nobody complained and everyone agreed to follow the orders.
One day a customer named Hongjun came looking for the company's miraculous medicine and asked for Jeongjeheon, the finely refined drug that ALPS is proud of. Under the resolutions every drug sits in a container whose capacity is the reciprocal of a positive integer, filled to the brim, and Jeongjeheon is in a beaker.
Jaeheon did not want to hand over the whole of Jeongjeheon. He decided to split it between a flask of capacity and a flask of capacity , give the flask to Hongjun and keep the flask in the company. But the flask is the one for sale and the flask is the one for storage. By the resolutions both flasks have to be completely full of Jeongjeheon.
While picking the two flasks, Jaeheon stopped selling anything and started wondering how many ways there are to split Jeongjeheon into two flasks without breaking the resolutions. Answer his question quickly so that Hongjun can finally buy his Jeongjeheon.
Input
The input consists of several lines, one test case per line. Each line gives the capacity of Jeongjeheon in the form 1/n, with . A line contains no whitespace. Read until the end of the input.
Output
For each test case, print on its own line the number of ways to split Jeongjeheon into the two flasks. That is, print the number of pairs of positive integers with . The pairs and differ only in order and count as one.