BigFatInteger.cpp

#include <bits/stdc++.h>
using namespace std;

class BigFatInteger
{
public:
	int minOperations(int A, int B);
};

int div1(int &A, int d) {
  int ret = 0;
  while(A % d == 0) {
    ret++;
    A/=d;
  }
  return ret;
}

int BigFatInteger::minOperations (int A, int B)  {
  int ret = 0;
  //int mn = 1e8;
  int mx = 0;
  //vector <int> mul;
  for(int i = 2; i <= A; i++) if(A % i == 0) {
    int cntTmp = div1(A, i);
    int cnt = cntTmp * B;
    ret++;

    int tmp = 0;
    while(cnt > 1) {
      int p;
      for(p = 0; (1<<p) < cnt && (1<<p) <= cnt; p++);
      p--;
      cnt -= (1<<p);
      tmp++;
    }
    mx = max(mx, tmp);
  }

  return ret + mx;
}

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit-pf 2.3.0
#include <iostream>
#include <string>
#include <vector>
#include <ctime>
#include <cmath>
using namespace std;
bool KawigiEdit_RunTest(int testNum, int p0, int p1, bool hasAnswer, int p2) {
	cout << "Test " << testNum << ": [" << p0 << "," << p1;
	cout << "]" << endl;
	BigFatInteger *obj;
	int answer;
	obj = new BigFatInteger();
	clock_t startTime = clock();
	answer = obj->minOperations(p0, p1);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << p2 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p2;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	bool disabled;
	bool tests_disabled;
	all_right = true;
	tests_disabled = false;
	
	int p0;
	int p1;
	int p2;
	
	// ----- test 0 -----
	disabled = false;
	p0 = 6;
	p1 = 1;
	p2 = 2;
	all_right = (disabled || KawigiEdit_RunTest(0, p0, p1, true, p2) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 1 -----
	disabled = false;
	p0 = 162;
	p1 = 1;
	p2 = 4;
	all_right = (disabled || KawigiEdit_RunTest(1, p0, p1, true, p2) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 2 -----
	disabled = false;
	p0 = 999983;
	p1 = 9;
	p2 = 5;
	all_right = (disabled || KawigiEdit_RunTest(2, p0, p1, true, p2) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 3 -----
	disabled = false;
	p0 = 360;
	p1 = 8;
	p2 = 8;
	all_right = (disabled || KawigiEdit_RunTest(3, p0, p1, true, p2) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 4 -----
	disabled = false;
	p0 = 2;
	p1 = 27;
	all_right = (disabled || KawigiEdit_RunTest(4, p0, p1, false, p2) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 5 -----
	disabled = false;
	p0 = 2;
	p1 = 32;
	all_right = (disabled || KawigiEdit_RunTest(5, p0, p1, false, p2) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	if (all_right) {
		if (tests_disabled) {
			cout << "You're a stud (but some test cases were disabled)!" << endl;
		} else {
			cout << "You're a stud (at least on given cases)!" << endl;
		}
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// This problem statement contains superscipts that may not display properly outside the applet.
// 
// Lun the dog loves very large integers. Her favorite is AB (A to the power of B).
// 
// 
// She has an integer variable X. Initially, the value of X is set to 1. She can perform the following two kinds of operations in any order, any number of times.
// 
// Operation 1: choose a prime number p, then multiply X by p.
// Operation 2: choose a positive divisor d of the value of X at that point, then multiply X by d.
// 
// 
// 
// You are given two ints A and B. Return the minimum number of operations Lun needs to perform
// in order to obtain X = AB from the initial state X = 1.
// 
// DEFINITION
// Class:BigFatInteger
// Method:minOperations
// Parameters:int, int
// Returns:int
// Method signature:int minOperations(int A, int B)
// 
// 
// CONSTRAINTS
// -A will be between 2 and 1,000,000 (106), inclusive.
// -B will be between 1 and 1,000,000 (106), inclusive.
// 
// 
// EXAMPLES
// 
// 0)
// 6
// 1
// 
// Returns: 2
// 
// Here, AB = 61 = 6. Here is one of the optimal sequences of operations:
// 
// Perform operation 1 by choosing p=2. X is now 1*2 = 2.
// Perform operation 1 by choosing p=3. X is now 2*3 = 6.
// 
// 
// 1)
// 162
// 1
// 
// Returns: 4
// 
// One of the optimal sequences of operations:
// 
// Perform operation 1 by choosing p=3. X is now 1*3 = 3.
// Perform operation 1 by choosing p=3. X is now 3*3 = 9.
// Perform operation 2 by choosing d=9. X is now 9*9 = 81.
// Perform operation 1 by choosing p=2. X is now 81*2 = 162.
// 
// 
// 2)
// 999983
// 9
// 
// Returns: 5
// 
// Here, A is prime. One of the optimal sequences of operations:
// 
// Perform operation 1 by choosing p=A. X is now A.
// Perform operation 1 by choosing p=A. X is now A2.
// Perform operation 1 by choosing p=A. X is now A3.
// Perform operation 2 by choosing d=A3. X is now A6.
// Perform operation 2 by choosing d=A3. X is now A9.
// 
// 
// 3)
// 360
// 8
// 
// Returns: 8
// 
// 
// 
// END KAWIGIEDIT TESTING