The Shakuni Game

*Author:* artha6391

*Tester:* anushka_nagar

*Editorialist:* august_24

# DIFFICULTY:

EASY

# PREREQUISITES:

Prime Factorization

# PROBLEM:

Given an integer N \geq 1, the following operations is performed until N becomes 1:

Choose an integer x \geq 1 that is divisible by N and divide N by x. If x is even, we get A points, else we get B points.

We need to find the maximum number of points achievable.

# EXPLANATION:

Let us first do the prime factorization of N. Let the total sum of even powers be even and the total sum of odd powers be odd.

For example, if N = 180, then N = 2^2 * 3^2 * 5^1. Therefore, even = 2 and odd = 2+1 = 3.

Now the problem can be solved in various cases depending on A and B:

Case 1: A \geq 0 and B \geq 0

• In this case, since both A and B are non-negative, we want to divide N as many times as possible by both even and odd primes.

• Therefore, in this case, the answer will be even * A + odd * B

Case 2: A \leq 0 and B \leq 0

• In this case, since both A and B are not positive, we don’t want to divide N many times as this could reduce the cost. We want to get it done in one go i.e, divide N by N itself.

• Therefore, in this case, the answer will be A if N is even or else it will be B.

Case 3: A \geq 0 and B \leq 0

• In this case, we want to divide N by 2 as many times as possible. We also want to avoid dividing N by odd numbers.

• Suppose y is the maximum odd number divisible by N. If N is even, the first step we could do is divide N by 2 * y and then keep on dividing N by 2. Or else y = N and we need to divide N by N itself.

• Therefore, in this case, the answer will be even * A if N is even or else it will be B.

Case 4: A \leq 0 and B \geq 0

• In this case, we want to divide N by odd primes as many times as possible. We also want to avoid dividing N by even numbers.

• Suppose N is odd. Then we can divide N as many times as possible by odd primes. If N is even, we want to remove the even part in one operation itself. Then we can continue removing odd primes one by one.

• Therefore, in this case, the answer will be odd * B if N is odd or else it will be odd * B + A.

# SOLUTIONS:

## Setter’s Solution

#include <bits/stdc++.h>

using namespace std;

int main()

{

int tests;

cin >> tests;

while (tests–)

{

int n, a, b;

cin >> n >> a >> b;

int even = 0, odd = 0;

while (n % 2 == 0)

{

n /= 2;

even++;

}

for (int i = 3; i * i <= n; i++)

{

if (n % i == 0)

{

while (n % i == 0)

{

n /= i;

odd++;

}

}

}

if (n != 1)

odd++;

int ans = 0;

if (a >= 0 && b >= 0)

{

ans = even * a + odd * b;

}

else if (a <= 0 && b <= 0)

{

if (even)

ans = a;

else

ans = b;

}

else if (a >= 0 && b <= 0)

{

if (even)

ans = even * a;

else

ans = b;

}

else if (a <= 0 && b >= 0)

{

if (even)

ans = a + odd * b;

else

ans = odd * b;

}

cout << ans << endl;

}

}

## Tester’s Solution

#include <bits/stdc++.h>

using namespace std;

int main()

{

int tests;

cin >> tests;

while (tests–)

{

int n, a, b;

cin >> n >> a >> b;

int even = 0, odd = 0;

while (n % 2 == 0)

{

n /= 2;

even++;

}

for (int i = 3; i * i <= n; i++)

{

if (n % i == 0)

{

while (n % i == 0)

{

n /= i;

odd++;

}

}

}

if (n != 1)

odd++;

int ans = 0;

if (a >= 0 && b >= 0)

{

ans = even * a + odd * b;

}

else if (a <= 0 && b <= 0)

{

if (even)

ans = a;

else

ans = b;

}

else if (a >= 0 && b <= 0)

{

if (even)

ans = even * a;

else

ans = b;

}

else if (a <= 0 && b >= 0)

{

if (even)

ans = a + odd * b;

else

ans = odd * b;

}

cout << ans << endl;

}

}

## Editorialist’s Solution

#include <bits/stdc++.h>

using namespace std;

int main()

{

int tests;

cin >> tests;

while (tests–)

{

int n, a, b;

cin >> n >> a >> b;

int even = 0, odd = 0;

while (n % 2 == 0)

{

n /= 2;

even++;

}

for (int i = 3; i * i <= n; i++)

{

if (n % i == 0)

{

while (n % i == 0)

{

n /= i;

odd++;

}

}

}

if (n != 1)

odd++;

int ans = 0;

if (a >= 0 && b >= 0)

{

ans = even * a + odd * b;

}

else if (a <= 0 && b <= 0)

{

if (even)

ans = a;

else

ans = b;

}

else if (a >= 0 && b <= 0)

{

if (even)

ans = even * a;

else

ans = b;

}

else if (a <= 0 && b >= 0)

{

if (even)

ans = a + odd * b;

else

ans = odd * b;

}

cout << ans << endl;

}

}