When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

piyushgoyal443's blog

By piyushgoyal443, history, 8 years ago, In English

this is my solution and it works


#include < iostream >

using namespace std;

int main()
{
    int a, b, div, rem;
    cin >> a >> b;
    int sum = a;
    while(a >= b)
    {
        div = a / b;
        sum += div;
        rem = a % b;
        a = div + rem;
    }
    cout << sum << endl;
    return 0;
}

[link to the problem] (http://codeforces.com/problemset/problem/379/A)
`

but I saw other people solutions and they have used a formula that calculates answer without any loop

 ans = (a * b — 1)/(b — 1) 

Can someone please help me how to get this formula?

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Please provide a link to the problem.

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

There is no var called 'mod' in your code

»
8 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

(sorry for my english) Given:

a = q1 * b + r1;   (1)
q1 + r1 = q2 * b + r2;   (2)
       ...
q(n - 1) + r(n - 1) = qn * b + rn;   (n) where qn = 0

ans = a + sum(i = 1 ... n - 1){qi}

Let s = sum(i = 1 ... n — 1){qi}

So we need to find s. From (1) we get r1:

r1 = a - q1 * b

From this and (2) we get r2:

r2 = a - q1 * (b - 1) - q2 * b

And so we get r3:

r3 = a - (q1 + q2) * (b - 1) - q3 * b

And so on:

rn = a - s * (b - 1) - qn * b = a - s * (b - 1)

Then

s = (a - rn) / (b - 1) (s)

if rn equals 0 then q(n — 1) + r(n — 1) = 0 too. And then q(n — 1) = 0 and n = n — 1 what is wrong. Then

1 <= rn < b

Then we need to subtract at least 1 from a in (3):

s = (a - 1) / (b - 1)

answer = a + s = a + (a - 1) / (b - 1) = (a * b - 1) / (b - 1)