2016 Personal Training #5 Div.2 Gym 100637J

C - 寅

Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

Submit  Status

Description

standard input/output 
Statements

On the most perfect of all planets i1c5l various numeral systems are being used during programming contests. In the second division they use a superfactorial numeral system. In this system any positive integer is presented as a linear combination of numbers converse to factorials:

Here a₁ is non-negative integer, and integers a_k for k ≥ 2 satisfy 0 ≤ a_k < k. The nonsignificant zeros in the tail of the superfactorial number designation  are rejected. The task is to find out how the rational number  is presented in the superfactorial numeral system.

Input

Single line contains two space-separated integers p and q (1 ≤ p ≤ 10⁶, 1 ≤ q ≤ 10⁶).

Output

Single line should contain a sequence of space-separated integers a₁, a₂, ..., a_n, forming a number designation  in the superfactorial numeral system. If several solution exist, output any of them.

Sample Input

Input

1 2

Output

0 1 

Input

2 10

Output

0 0 1 0 4 

Input

10 2

Output

5 

唉，弄半天真是贪心，当时错两边就没再仔细看，倒是卡在数据类型半天。

题意：给你p，q输出满足公式的ai，

思路：从a1开始，a2=p*2!/q，...;直到p为零结束。有个小疑问0<=ak<k这个条件好像没什么用？难道其中有什么...。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
int main()
{
  LL p,q;
  scanf("%lld%lld",&p,&q);
  for(int i=2;;i++)
  {
    int ans=p/q;
    if(ans>=i&&i!=2)
    {
      ans=i-1;
    }
    p=(p-ans*q)*i;
    printf("%d",ans);
    if(p==0)
    {
      printf("\n");break;
    }
    printf(" ");
  }
}