I tried to solve this problem,got AC but only 15 points as I could not complete the second subtask.I saw someone else’s solution who had gotten 100 points(completing both the subtasks).He used some weird gcd and lcm concept to get the answer.Please help me understand why my code does not accomplish both the subtasks and his does.Here is my solution and here is the other person’s solution.Thanks in advance.
N can be upto 10^{18}, so iterating over N will definitely exceed the time limit. Number of multiples of a number X less than number Y is equal to Y/X. So, numbers that are multiple of A and less than N will be N/A and for B it will be N/B but it will also count twice those numbers which are divisible by both A and B so we need to subtract those numbers twice. If A and B are co-prime then such numbers will be simply N/(A*B) but if they aren’t co-prime then you’ll miss some numbers example: consider A=15, B=25 and N=100 then A*B=475, and multiples of A = \{15,30,45,60,75,90\} and multiples of B =\{25,50,75,100\}, if you divide N by A*B to count the multiples which are divisible by both A and B then you’ll get 0 as [100/475]=0 which is incorrect, but actually we have to divide N by the LCM of A and B which is nothing but (A*B)/gcd(A,B)=75.
Oh thank you very much.Now I understood his logic and why he got 100 points.I was curious if you could suggest me any sources or any ways in which I can study and myself have such ideas to solve a programming problem efficiently.Thank you so much for your
help.