kaffan_69's blog

By kaffan_69, history, 4 years ago, In English

please help me with this greedy problem

D fraction Now Arnab is given a fraction N/D . He is asked to divide the fraction in sum of unique unit fractions where N/D=(1/D1)+(1/D2)+(1/D3)+...+(1/Dn). Now find the value of D1,D2,....,Dn.

if (1/Di)=2 then value of Di=1/2, print it in fraction as 1/2 not as floating point number.

Input format The first line contains an integer T , denoting the number of test cases. For each test case, there are two space-separated integers N and D.

Output format For every testcase on a new line, print space separated values of D1,D2,....,Dn.

Constraints: 1<=T<=10 1<=N,D<=10000

Example Input 1 2 3

Output 2 6

Explanation We know, 2/3=1/2+1/6.

  • Vote: I like it
  • +1
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What greedy problem?

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Same problem, I think this Egyptian fraction method can help you, I'm reading it too