博客

题目描述

一个正整数一般可以分为几个互不相同的自然数的和，如 3=1+23=1+2，4=1+34=1+3，5＝1+4=2+35＝1+4=2+3，6=1+5＝2+46=1+5＝2+4。

现在你的任务是将指定的正整数 n

n

分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。

输入格式

只一个正整数 n

n

，（3 \leq n \leq 100003≤

n

≤10000）。

输出格式

第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。

第二行是最大的乘积。

输入输出样例

输入 #1

复制

10

输出 #1

复制

2 3 5
30

import java.math.*;
import java.lang.*;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		Long n = scanner.nextLong();
        int k  = (int)(Math.sqrt(new BigInteger(String.valueOf((9+8*n))).doubleValue()) - 1)/2 + 1;
        BigInteger sum;
        sum = new BigInteger(String.valueOf((k-1)*(2+k)>>1)).subtract(new BigInteger(String.valueOf(n)));
        BigInteger count =new BigInteger("1");
        for (int i = 2; i <= k; i++) {
            if(sum.intValue() == i)continue;
            System.out.print(i+" ");
            count = count.multiply(new BigInteger(String.valueOf(i)));
        }
        System.out.println();
        System.out.println(count);
    }
}