UVa 550 - Multiplying by Rotation

Accepted date: 2011-08-06
Ranking (as of 2013-08-03): 250 out of 940
Language: C++

/*
  UVa 550 - Multiplying by Rotation

  To build using Visual Studio 2008:
    cl -EHsc -O2 multiplying_by_rotation.cpp
*/

#include <iostream>
using namespace std;

int main()
{
  int base, first_factor, multiplier;
  while (cin >> base >> first_factor >> multiplier) {
    int n = 0, multiplicand = first_factor;
    for (int carry = 0; ; n++) {
      int product = multiplicand * multiplier + carry;
      carry = product / base;
      if (!carry && product == first_factor)
        break;
      multiplicand = product % base;
    }
    cout << n + 1 << endl;
  }
  return 0;
}