Recently, I was trying to solve a problem. To solve that I shall have to solve a sub problem. The sub problem is:

I will be provided some values. I want to find number of pairs possible for that set of values who have gcd>1

Can anyone suggest an efficient approach? I just want you to give me hints so that I can start from that point of view and move forward.

**Solution link:** https://ideone.com/Mf1Igo  

**Problem Link:** [Inversion Sort from SPOJ ](https://www.spoj.com/problems/INVESORT/)

**Verdict:** TLE

I have read the editorial but yet not cleared enough about the approach. Can anyone provide me some hints? How to approach this problem? I just need to know about the observation that how you will approach the problem to solve it.

Problem

A pattern can be seen in the solution that the result will be equal to (n/2)*m . May be I am missing any mathematical concept behind this reason. Can anyone provide me the mathematical logic behind the solution? Why is this working?

Problem: https://vjudge.net/problem/LightOJ-1294

Sometimes, some problem teaches us how to focus on a problem and think of it differently.. Actually, these kind of observations just make me wondered..

For example : 6x -3 this is equation can be seen as 3(2x-1) which means if we put integer values of x then this equation will give us multiple of 3. So these kind of querys like if it is possible to obtain a value V from this equation putting some integer values of x ; can be observed from this equation.. When I was in high school, I didn’t think over any equations. Just solved them. But observing any equation is much more important. While thinking over such problems i only note down what kind of new observations I got that could help me in future.

I want to know more From you. Hope it will actually help new problem solvers. I also want some observations observed by you that may help others to think over a problem more precisely and accurate way. Which observations made you wondered and pleased and made you think "OMG! this can be viewed like this! Couldn’t think of it "

Idea at a glance: I precalculated all the sum of phi() values till some range. Then while for some query I ran a binary search on the precalculated sum of the euler values.... So according to this process complexity should be O(n) + T*(log(n)

Problem:

https://algo.codemarshal.org/contests/icpc-dhaka-19-preli/problems/G

If needs to sign up to see the problem then please check this drive link ( problem number G) to see the problem

Drive link :
https://drive.google.com/file/d/10k4fXa1SZWQM79XbwONUMyAWk70zwMCt/view?usp=drivesdk

My code:

https://pastebin.com/XcvSPtse

I found the problem interesting. Can anyone share the idea behind this problem? I have attached the problem link with this post but may be you need to sign up to see the problem. So I have also attached the Google Drive link of this problem

main source: https://algo.codemarshal.org/contests/icpc-dhaka-19-preli/problems/G

Drive link: Problem number: G (Pairs forming GCD ) https://drive.google.com/open?id=10k4fXa1SZWQM79XbwONUMyAWk70zwMCt

https://forthright48.com/spoj-lcmsum-lcm-sum/

I found this blog extremely helpful . But I can't understand one line. If anyone summarize it to me then it would be helpful. It says ,

"How many values i can we put such that gcd(i,n)=d? There are ϕ(n/d) possible values of i for which we get gcd(i,n)=d. "

My question is how we can conclude this that ; number of possible pairs for any i with n where gcd(i,n) = d will be phi(n/d) ? Can anyone explain it ? Or suggest some blog that can actually help me to understand the concept.

Thanks in advance