PROBLEM LINK:
Setter: Soumyadeep Pal
Tester: Samarth Gupta
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
SIMPLE
PREREQUISITES:
Prime factorization
PROBLEM:
Given an integer N \gt 1, the following operations is performed until N becomes 1:
- Choose an integer x \gt 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^23^25^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: \hspace{1 mm} 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 \cdot A +odd\cdot B.
Case 2: \hspace{1 mm} 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: \hspace{1 mm} A \geq 0 and B \leq 0
-
In this case, we wan’t to divide N by 2 as many times as possible. We also wan’t 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 \cdot 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 \cdot A if N is even or else it will be B.
Case 4: \hspace{1 mm} 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\cdot B if N is odd or else it will be odd \cdot B + A.
TIME COMPLEXITY:
O(\sqrt N) for each testcase for doing the prime factorization of N.
SOLUTION:
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;
}
}
Setter's solution
#include<bits/stdc++.h>
using namespace std;
template <class T> ostream &operator << (ostream &os, const vector<T> &p) { os << "["; for (auto&it : p) os << it << " "; return os << "]";}
template <class S, class T> ostream &operator << (ostream &os, const pair<S, T> &p) { return os << "(" << p.first << "," << p.second << ")";}
#ifndef ONLINE_JUDGE
#define deb(...) dbs(#__VA_ARGS__,__VA_ARGS__)
template <class T> void dbs(string str, T t) { cerr << str << ":" << t << "\n";}
template<class T, class...S> void dbs(string str, T t, S... s) { int idx = str.find(','); cerr << str.substr(0, idx) << ":" << t << ","; dbs(str.substr(idx + 1), s...);}
#else
#define deb(...){}
#endif
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || ( cnt == 19 && fi > 1) ));
} else if (g == endd) {
if (is_neg) {
x = -x;
}
deb(l, r, x);
assert(l <= x && x <= r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert(g != -1);
if (g == endd) {
break;
}
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
return readString(l, r, ' ');
}
#define int long long
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define pr(x) {cout << x << '\n'; return;}
#define nl cout<< '\n'
#define rep(i,n) for(int i = 0; i < n; i++)
#define re(i,n) for(int i = 1; i <= n; i++)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
template<class T> inline T Bit(T x, int i) { return (x >> i) & 1;}
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
// const int N = 1e5 + 3; // check the limits
void solve(int tc) {
int n, a, b;
n = readIntSp(2, 1e9);
a = readIntSp(-1e3, 1e3);
b = readIntLn(-1e3, 1e3);
int even = 0, odd = 0;
for (int i = 2; i * i <= n; i++) {
while (n % i == 0) {
n /= i;
if (i % 2) odd++;
else even++;
}
}
if (n > 1 && n % 2) {
odd++;
}
if (n > 1 && n % 2 == 0) {
even++;
}
int ans = 0;
if (a >= 0) ans += even * a;
else if (even > 0) ans += a;
if (b >= 0) ans += odd * b;
else if (even == 0 && odd > 0) ans += b;
cout << ans << '\n';
}
signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = readIntLn(1, 500);
for (int i = 1; i <= t; i++) solve(i);
assert(getchar() == -1);
return 0;
}
Tester's solution
t = int(input())
for _ in range(t):
n, a, b = map(int, input().split())
i = 2
even_sum, odd_sum = 0, 0
while(i * i <= n):
if(n%i == 0):
cnt = 0
while(n%i == 0):
cnt += 1
n /= i
if(i%2 == 0):
even_sum += cnt
else:
odd_sum += cnt
i += 1
if(n > 1):
if(n%2 == 0):
even_sum += 1
else:
odd_sum += 1
ans = 0
if(a >= 0):
ans += (a*even_sum)
elif(even_sum > 0):
ans += a
if(b >= 0):
ans += (b*odd_sum)
elif(even_sum == 0 and odd_sum > 0):
ans += b
print(ans)
Please comment below if you have any questions, alternate solutions, or suggestions.