First divide by 2 and then divide by 6 directly to get 1. Since you divided by an even number each time, your total score will 2+2 = 4. Notice that when we have odd factors, we have can skip dividing by them, by simply stopping at the moment in time when only a single 2 is left in the prime factorization.
1 Like
Spoiler
12 = 2*6 which gives (2+2 = 4)
If Codechef provide the hacking like Codeforces, I will hack everyone’s code (at least python3).
T = 2000
N <= 10^9
Overall = 2000 x 3 x 10000 = 6 x 10^7 (Not possible in 2.5 second)
1 Like
you can type your testcase i’ll more than happy to run it over my solution.
You can find my solution in the upper comments.
Can please anyone tell me where I am making the mistake
My concept is first to find all the prime factors of n and their count and then if the factor is even then multiply the count by a otherwise b and add it to ans.
https://www.codechef.com/viewsolution/52392432
map stores all the factors as key and their count as value
or please tell me on which test case this code fails
I dont know why my solution is giving WA -
I have considered every scenario (might not be exactly same as editorial) -
Edit - This code works fine now:
#include<bits/stdc++.h>
using namespace std;
void Optimized(long long n , long long &even , long long &odd)
{
for(long long i=2 ; i*i<=n ;i++)
{
if(n%i == 0)
{
long long cnt =0;
while(n %i == 0)
{
cnt++;
n= n/i;
}
if(i%2 == 0)
even += cnt;
else
odd +=cnt;
}
}
if(n >1)
{
if(n%2 == 0)
even++;
else
odd++;
}
}
int main()
{
int t;
cin >> t;
while(t--){
long long n , a, b;
cin >> n >> a >> b;
long long even = 0,odd = 0;
Optimized(n,even,odd);
long long ans = INT_MIN;
if(a>=0 && b>=0)
{
ans = (even *a) + (odd*b);
}
else if(a>=0 && b<0)
{
if(n%2 == 0)
{
ans = even*a;
}
else{
ans = b;
}
}
else if(a<0 && b>=0)
{
if(n%2 == 0)
{
ans = max(b*odd + a , a);
}
else{ ///it does not contain any even part
ans = b*odd;
}
}
else if(a<=0 && b<=0){
if(n%2 == 0)
ans = a;
else
ans = b;
}
cout << ans << endl;
}
return 0;
}
I have handled all the cases. Yet my code is giving WA.
Can anyone check where I am wrong.
Here is my solution:
https://www.codechef.com/viewsolution/52342895
1 Like
Bro, can you tell me any corner case which I am missing?
https://www.codechef.com/viewsolution/52370165
why my code is not working?
#include
#include<stdio.h>
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
int evenpoints(int n,int a)
{
int b,s=0;
while (n%2==0)
{
s+=a;
n=n/2;
}
return s;
}
int oddpoint(int n,int b)
{
int i,a,s=0;
for(i=3;i<=n;i+=2)
{
while (n%i==0)
{
s+=b;
n=n/i;
}
}
return s;
}
int main()
{
int t;
cin>>t;
while (t--)
{
int pe,po,n,a,b;
cin>>n>>a>>b;
if (a<0 and b<0)
{
if(n%2==0)
cout<<a;
else
cout<<b;
}
else if(a>=0 and b<0)
{ pe=evenpoints(n,a);
if(n%2==0)
cout<<pe;
else
cout<<po;
}
else if(a<0 and b>=0)
{ po=oddpoint(n,b);
if(n%2==0)
cout<<a+po;
else
cout<<po;
}
else if(a>=0 and b>=0)
{
pe=evenpoints(n,a);
po=oddpoint(n,b);
cout<<pe+po;
}
cout<<endl;
}
}
can you share the code which gives correct output for
above testcase.thnx
#include
#include
#include
using namespace std;
int main()
{int T;
cin>>T;
while(T–)
{
int n,A,B;
cin>>n>>A>>B;
vectorvt;
int sum=0;
while(n%2==0)
{
vt.push_back(2);
n=n/2;
}
for(int i=3;i<=sqrt(n);i+=2)
{
while(n%i==0)
{
vt.push_back(i);
n=n/i;
}
}
if(n>2)
vt.push_back(n);
if(B<0)
cout<<B<<endl;
else if (A<0)
cout<<A<<endl;
else
{
for(auto i: vt)
{
if(i%2==0)
sum+=A;
else
sum+=B;
}
cout<<sum<<endl;
}
}
return 0;
}
it is giving correct output but showing wrong answer
yeah i am also having same problem
When there is negative score for odd factors the logic is:
→ To club all the odd factors together to form 1 odd number.
→ Then again convert that ODD number to even, if there is atleast one 2 present as factor. Hence making number of ODD divisors as 0.
→ If there are no 2 as factor, so the multiplication of all ODD factors will be that number itself. i.e 1 ODD number
The answer to this testcase is supposed to be 0
1
10 -1 1
Thanks brother, i have corrected it and now it’s accepted🤗
This is not expected and so annoying that n was the range 1e9 and testcases too 1e3 , and then the solution has o(sqrtn) time complexity , i figured out the solution as soon as i saw the problem , but just because of the fact that n was large , i thought if there existed some better optimization but turns out that that main solution had sqrtn 
**PLEASE HELP ME.I DON’T UNDERSTAND WHY IT IS GIVING WRONG ANSWER. **
I AM A BEGINNER AND TRYING TO SOLVE THIS QUESTION BUT IT IS GIVING WRONG ANSWER.
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
long long int div(long long int n, long long int a, long long int b)
{
if (n == 1)
{
return 0;
}
if (a == 0 && b == 0)
{
return 0;
}
long long int divisor = 0;
if (a >= 0 && b >= 0)
{
if (n % 2 == 0) //FOR EVEN
{
return a + div(n / 2, a, b); //CAN GO TO ODD AS WELL
}
else //FOR ODD
{
if (b == 0)
{
return 0;
}
// FIND THE FIRST ODD DIVISOR OF N
for (long long int i = 3; i <= sqrt(n); i += 2)
{
if (n % i == 0)
{
divisor = i;
break;
}
}
if (!divisor) //MEANS CAN'T FIND ANY DIVISOR SO PRIME NO.
{
return b;
}
else
{
return b + div(n / divisor, a, b);
}
}
}
if (a >= 0 && b < 0)
{
if (n % 2 == 0)
{
if (a == 0)
{
return 0;
}
long long int x = n, sum = 0;
while ((x != 1) && x % 2 == 0) //DON'T GO TO ODD NO.
{
sum += a;
x /= 2;
}
return sum;
}
else
{
return b; //WE CAN'T GET EVEN NO. AFTER DIVIDING ODD BY ODD
}
}
if (a < 0 && b >= 0)
{
if (n % 2 == 0)
{
if (b == 0)
{
return a;
}
for (long long int i = 2; i <= sqrt(n); i += 2)
{
if (n % i == 0 && ((n / i) % 2) == 1) //WE CAN GO IN ODD NO. ONLY
{
divisor = i;
break;
}
}
if (!divisor)
{
return a;
}
else
{
return a + div(n / divisor, a, b);
}
}
else
{
for (long long int i = 3; i <= sqrt(n); i += 2) //FIND THE FIRST ODD DIVISOR
{
if (n % i == 0)
{
divisor = i;
break;
}
}
if (!divisor)
{
return b;
}
else
{
return b + div(n / divisor, a, b);
}
}
}
if (b < 0 && a < 0)
{
if (n % 2 == 0)
{
return a;
}
else
{
return b;
}
}
return -1;
}
int main()
{
int t;
cin >> t;
while (t--)
{
long long int n, a, b;
cin >> n >> a >> b;
cout << div(n, a, b) << endl;
}
return 0;
}
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tc;
cin >> tc;
while(tc–)
{
int n, a, b;
cin >> n >> a >> b;
int eve = 0, odd = 0;
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
while (n % i == 0)
{
n /= i;
if(i%2 == 0)
eve++;
else
odd++;
}
}
}
if (n != 1)
odd++;
int res = 0;
if (a >= 0 && b >= 0)
{
res = eve * a + odd * b;
}
else if (a <= 0 && b <= 0)
{
if (eve)
res = a;
else
res = b;
}
else if (a >= 0 && b <= 0)
{
if (eve)
res = eve * a;
else
res = b;
}
else if (a <= 0 && b >= 0)
{
if (eve)
res = a + odd * b;
else
res = odd * b;
}
cout << res << endl;
}
}
why it gives error in one subtask