Techniques and Solutions of Problems LightOJ - 1007 , LightOJ - 1014, LightOJ - 1024 , LightOJ - 1028 , LightOJ - 1035

In this article I am writing some of my techniques in describe which I have used to solved the following problems:

1. LightOJ - 1007 Mathematically Hard
2. LightOJ - 1014 Ifter Party
3. LightOJ - 1024 Eid
4. LightOJ - 1028 Trailing Zeroes (I)
5. LightOJ - 1035 Intelligent Factorial Factorization

Please follow the above sequences one by one to get your desired problem.

1. LightOJ - 1007 Mathematically Hard

 

Technique: This is an exact application of Prime Numbers. In this problem just one variance is used and this is called Euler Phi. If you have no idea about Euler phi then please learn the basic from here. you should see that there is an equation which can find the number of relative prime smaller than a particular number.Say the number is n, then the Phi of n is defined as the number of relative prime smaller then n.

OK. We have just got the equation in above picture. There, P1, P2,...Pm are the primes that divides the number(n) and e1,e2,...,em are the exponent or the number of times a particular prime divides the number(n).
Since we have to multiply n hence we would multiply every number in the array by that line:
for(i=2;i<=5000000;i++) res1[i]=i; 
 
To solve this,  You need to first generate primes till the desired number. Then there is a technique which will help you to skip the time limit exceed verdicts. For every prime you just calculate its part for the numbers it divides.

2. LightOJ - 1014 Ifter Party    

 

Technique: Read carefully, you'll notice that P-L number piaju's are left. When no contestant can eat any piaju's then the case will be "impossible".
Now for possible case: There's no restriction in contestant number. It means that contestant number can be any value. You have to find the number of piaju's each contestant ate. So, each contestant can ate any number of piaju's which divides the P-L value. Suppore, if P-L is 4, then contestant can ate 1,2 or 4 piaju's each since they divides 4. Contestant can't ate 3 piaju's since it doesn't divides 4. So, we can divide P-L by all value less then P-L to check which value divides it and the value must be greater then L since it has been told that L<Q . 
An optimization is square root the P-L since dividing by the value of one site of square root value we could get the value of other site.

3. LightOJ - 1024 Eid  

 

Technique: This is a very interesting problem . I am describing it in a very simple straightforward way. Listen, You are given some de-sec. You are told to find such a de-sec (EID) in which all the races eat together. So, what you have understood?? You are given some number. Find the number which is divisible by all of them. Are you getting any coincidence among them. Yes!! This is a LCM,i mean, Longest Common Multiple problem. But, the problem is here you have to find the longest common multiple of maximum approximately 1000 numbers. So, the resultant number could be very big and overflow the long long int too. So, You need to do array manipulation. Did you know the prime factorization mathod to find LCM? This is necessary here. You can check my code below to understand the LCM procedure. But, Try yourself.

4. LightOJ - 1028 Trailing Zeroes (I)

 

Technique: Have you any idea about the finding the number of divisors of a number? This problem is a of that type. Here, Since you are said to find such a base in which trailing zeros exist so it can be assumed that if we can find the number of divisor of that number then the problem can be solved easily. Have you any idea? 
Suppose n is a number and its prime factorization is n=P1^x * P2^y. Then the number of divisors of n is = (x+1)*(y+1).
Suppose n=6, then 6= 2^1*3^1. Now, Number of divisor = (1+1)*(1+1)=4.
So, After prime generation just do this work and this is the result.

5. LightOJ - 1035 Intelligent Factorial Factorization

 

Technique: I Think you should get the technique to solve this problem yourself. You could have implementation problem. However, I am helping you in both case here. In this problem since you have to do prime factorization till N! (1,2,3,..,N) So, what you need to do extra is memorize the prime factorization of a number and add it with the factorization of next number till 1 to N. In my code, I did this.


If you have any problem understanding then leave a comment.