3136375_ce.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;
import java.math.*;

public class Main
{
	public static void main(String [] args)
	{
		Scanner cin = new Scanner (System.in);
		BigInteger sum, min, max, tmp, mid, tt;
		BigInteger one, two, six;

		one = BigInteger.ONE;
		two = BigInteger.valueOf(2);
		six = BigInteger.valueOf(6);

		sum = cin.nextBigInteger();
		min = BigInteger.ZERO;
		max = sum;
		while(min.compareTo(max)<0)
		{
			mid = min.add(max).divide(two);
			tmp = mid.multiply(mid.add(one)).multiply(mid.multiply(two).add(one)).divide(six);
			int t = tmp.compareTo(sum);

			if(t <= 0)
			{
				min = mid.add(one);
			}
			else
			{
				max = mid;
			}
		}

		tmp = min;

		int cnt = 0;
		int [][] ans = new int [100][2];

		BigInteger tt;
		min = BigInteger.ZERO;
		max = sum;
		while (min.compareTo(max) < 0)
		{
			mid = min.add(max).divide(two);
			if (mid.add(mid) <= sum)
				min = mid.add(one);
			else
				max = mid.subtract(one);
		}
		tt = min;
		for(int l = tmp.intValue(); l > 0; l--)
		{
			boolean flag = false;
			min = BigInteger.ZERO; max = min;
			while(min.compareTo(max)<=0)
			{
				mid = min.add(max).divide(two);
				if(mid.compareTo(BigInteger.valueOf(l))<0)
				{
					min = mid.add(one);
					continue;
				}
				tmp = mid.multiply(mid).multiply(mid).multiply(two).add(mid.multiply(mid).multiply(one.add(two))).add(mid);
				tt = mid;
				mid = mid.subtract(BigInteger.valueOf(l));
				tmp = tmp.subtract(mid.multiply(mid).multiply(mid).multiply(two).add(mid.multiply(mid).multiply(one.add(two))).add(mid));
				tmp = tmp.divide(six);
				mid = tt;
				int t = tmp.compareTo(sum);
				if(t==0)
				{
					min = mid;
					flag = true;
					break;
				}
				else
				{
					if(t<0)
						min = mid.add(one);
					else
						max = mid.subtract(one);
				}
			}
			if(flag)
			{
				ans[cnt][0] = l;
				ans[cnt][1] = min.intValue();
				cnt++;
			}
		}
		System.out.println(cnt);
		for(int i = 0; i < cnt; i++)
		{
			System.out.print(ans[i][0]);
			for(int j = ans[i][1]-ans[i][0]+1; j <= ans[i][1]; j++)
			{
				System.out.print(" "+j);
			}
			System.out.println();
		}
	}
}