ZOJ 3768 Continuous Login

Description

Pierre is recently obsessed with an online game. To encourage users to log in, this game will give users a continuous login reward. The mechanism of continuous login reward is as follows: If you have not logged in on a certain day, the reward of that day is 0, otherwise the reward is the previous day's plus 1.

On the other hand, Pierre is very fond of the number N. He wants to get exactly N

Input

There are multiple test cases. The first line of input is an integer T

There is one integer N (1 <= N

Output

For each test case, output the days of continuous login, separated by a space.

This problem is special judged so any correct answer will be accepted.

Sample Input

4

20

19

6

9

Sample Output

4 4

3 4 2

3

2 3

Hint

20 = (1 + 2 + 3 + 4) + (1 + 2 + 3 + 4)

19 = (1 + 2 + 3) + (1 + 2 + 3 + 4) + (1 + 2)

6 = (1 + 2 + 3)

9 = (1 + 2) + (1 + 2 + 3)

Some problem has a simple, fast and correct solution.

首先要判斷出最多三個數即可，即2N=x*x+y*y+z*z+x+y+z有非負整數解。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
int T, n, f[3];

int check(int x)
{
  long long a = 8 * x + 1, b = sqrt(a);
  if (b*b == a) return (b - 1) >> 1;
  else return 0;
}

void work(int x)
{
  f[0] = f[1] = f[2] = 0;
  if (check(x)) { f[0] = check(x); return; }
  int a = int(sqrt(double(8 * x + 1)) - 1) >> 1;
  for (int i = a; i > 0; i--)
  {
    f[0] = i;
    int y = x - (i * (i + 1) >> 1);
    if (y > x / 2) break;
    if (check(y)) { f[1] = check(y); return; }
  }
  for (int i = a; i > 0; i--)
  {
    f[0] = i;
    int y = x - (i * (i + 1) >> 1);
    int b = int(sqrt(double(8 * y + 1)) - 1) >> 1;
    for (int j = b; j > 0; j--)
    {
      f[1] = j;
      int z = y - (j * (j + 1) >> 1);
      if (z > y / 2) break;
      if (check(z)) { f[2] = check(z); return; }
    }
  }
}

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d", &n);
    work(n);
    printf("%d", f[0]);
    for (int i = 1; i < 3;i++) if (f[i]) printf(" %d", f[i]);
    printf("\n");
  }
  return 0;
}