ZOJ-3768：Continuous Login（打表找规律+暴力）

Continuous Login

---

Time Limit: 2 Seconds       Memory Limit: 131072 KB       Special Judge

---

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 points reward with the least possible interruption of continuous login.

Input

There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:

There is one integer N (1 <= N <= 123456789).

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.

思路：打表发现每个数最多只需3个数来表示，且如果这个数需要3个数表示，那么其组合中一定存在一个小于10的数。如此一来就可以n^(3/4)的复杂度暴力循环了。

#include<bits/stdc++.h> using namespace std; const int MAX=1e6; const int MOD=1e9+7; typedef long long ll; ll check(ll n) //判断n是否等于x*(x+1)/2 { ll x=sqrt(2*n); for(x-=2;x*(x+1)/2<=n;x++)if(x>0&&x*(x+1)==2*n)return x; return 0; } int main() { int T;cin>>T; while(T--) { ll n; scanf("%lld",&n); ll x=check(n); if(x*(x+1)==2*n)cout<<x<<endl; else { for(ll i=1;i*(i+1)/2<=n;i++) { x=check(n-i*(i+1)/2); if(x>0) { printf("%lld %lld\n",min(x,i),max(x,i)); goto nex; } } for(ll i=1;i*(i+1)/2<=n;i++) { for(ll j=1;j*(j+1)/2<=n-i*(i+1)/2;j++) { x=check(n-i*(i+1)/2-j*(j+1)/2); if(x>0) { printf("%lld %lld %lld\n",i,j,x); goto nex; } } } } nex:; } return 0; }