Fuzhou University OnlineJudge 
提示: 欢迎访问OurACM平台。
Problem 1607 Greedy division

Accept: 498    Submit: 1768
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Oaiei has inherited a large sum of wealth recently; this treasure has n pieces of golden coins. Unfortunately, oaiei can not own this wealth alone, and he must divide this wealth into m parts (m>1). He can only get one of the m parts and the m parts have equal coins. Oaiei is not happy for only getting one part of the wealth. He would like to know there are how many ways he can divide the wealth into m parts and he wants as many golden coins as possible. This is your question, can you help him?


There are multiply tests, and that will be 500000. For each test, the first line is a positive integer N(2 <= N <= 1000000), N indicates the total number of golden coins in the wealth.


For each test, you should output two integer X and Y, X is the number of ways he can divide the wealth into m parts where m is large than one, Y is the number of golden coins that he can get from the wealth.

Sample Input

5 6 8

Sample Output

1 1 3 3 3 4


There are huge tests, so you should refine your algorithm.



Submit  Back  Status  Discuss