# MULDIV - Editorial ( NCC 2014 )

Contest

Practice

SIMPLE

### PROBLEM:

F:

for i from 1 to M inclusive, do

``````if N is a multiple of K,

divide N by K

else,

multiply N by K
``````

print N

Perform the operation F on N.

### QUICK EXPLANATION:

The given pseudo code’s complexity will be O(M) and 1<=M<=10^10
Hence, directly implementing the pseudo code will result in TLE.

### EXPLANATION:

If N is not divisible by K, then the answer for the problem will be either N or KN.
If M is odd, then the answer will be K
N, else it will be N
If N is divisible by K, then we go on dividing N by K until it is no more divisible by K, once the value of N is not divisible by K, we can easily find out the answer. As, the answer now can be either N or N*K.

Note that while dividing N by K, it should not be divided more than M times.

The pseudo code will be:

``````
if K == 1:
else:
while N%K==0 and m!=0:
N = N/K
M = M-1
if M%2==1:
N*=K

``````

Complexity: O( log(M)/log(K) )

3 Likes

``````#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <climits>
#include <set>
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t--)
{
long long int N,M,K;
cin >> N >> K >> M;
if(N%K == 0)
{
long long int KK = K*K;
while(N%KK==0) { KK *= K*K;}
N = N%KK;
if(M%2==0)
cout << N << endl;
else
cout << N/K << endl;
}
else
{
if(M%2==0)
cout << N << endl;
else
cout << N*K << endl;
}
}
return 0;
}
``````

Any tips?

Your code will loop infinitely for k = 1.

1 Like

For K=1 your program will go into an infinite loop.

1 Like

``````#include<stdio.h>
int scan(){
long long int t=0;
char c;
c=getchar_unlocked();
while(c<'0' || c>'9')
c=getchar_unlocked();
while(c>='0' && c<='9'){
t=(t<<3)+(t<<1)+c-'0';
c=getchar_unlocked();
}
return(t);
}

int main(void)
{
long long int t,n,k,m;
t=scan();
getchar();
while(t--)
{
n=scan();
getchar();
k=scan();
getchar();
m=scan();
getchar();
if(k==1)
{
printf("%lld\n",n);
}
else if(k!=0){
if(n%k==0)
{
if(m%2==0)
printf("%lld\n",n);
else
printf("%lld\n",n/k);
}
else
{
if(m%2!=0)
printf("%lld\n",n*k);
else
printf("%lld\n",n);
}
}
}
return 0;
}``````

do cout.tie(NULL) as well

your code give wrong for test case
243 3 2
ans is 27 your code gives 243(which is wrong).

@karankapoor you have to divide n by k till you dont get it is divisible…but in any case you are diving only by once! so correct that and read editorial once you will get it

Happy coding.

I am getting a wrong answer for this code. I have tried almost all corner cases. still not able to understand where I am going wrong. Please help.

``````#include <stdio.h>
int main()
{
unsigned int t;
unsigned long int u,n,m,c,k,i,count;
scanf("%d",&t);
while(t--)
{
count=0;
scanf("%ld %ld %ld",&n,&k,&m);
u=m;
if(k==1)
printf("%ld\n",n);
else
{
if(n%k!=0)
{
if(m%2==0)
printf("%ld\n",n);
else
printf("%ld\n",k*n);
}
else
{
while((n%k==0)&&(m!=0))
{
n=n/k;
m--;
count++;
}
c=u-count;
if(c%2==0)
printf("%ld\n",n);
else
printf("%ld\n",k*n);
}
}
}
return 0;
``````

}