The following problems involve a sum of gcd. And this particular type of ideas are needed in some other problems too.
The first problem can solved by brute-force. But the latter problems will get you a TLE. So, we need to be tricky here. Let's assume we already know what Euler's Totient Function is and how to compute it efficiently. First we analyze the last problem. We need a lemma.
Lemma If d is a divisor of n, then there are Phi(n/d) numbers i <= n for which gcd(i,n)=d
Proof: We can see an example which certainly generalizes. Say, n=12 and we want to compute the number of numbers i <= 12 so that gcd(i,12)=3. Let's do it by hand first. These i are 3,9. Now, we compute it by logic.
First off, any such i must be divisible by 3. So, assume i=3j. Then gcd(12,3j)=3*gcd(j,4). Now, if gcd(4,j) is greater than 1, then our desired gcd will be greater than 3. Therefore, we must have gcd(4,j)=1. How many such j are there? Phi(4). So, the number of such i is the number of such j, i.e. Phi(4)=Phi(12/3). You can check it with other examples. And generally, it follows that for a divisor d, we would have such Phi(n/d) numbers.
According to the problem 4, we need to find the number of such numbers i <= n such that gcd(i,n) <= x. Again, gcd(i,n) is always a divisor of n. So, the divisors which are less than x will come in this gcd. We can write this as a sum of Phi(n/d) where d are divisors of n less than x. For this particular problem, we need to store the values of Phi(n/d) and their cumulative sum, to get them within O(1) query. Otherwise the program will be timed out. Also to find the greatest divisor of n less than or equal to x, a linear search won't be enough. You will need binary search.
The first 3 problems are the same, only the variation is in the limit. We solve the 3rd without loss of generality.
We are asked to find
We denote the sum by G(n) for a particular n for convenience. First, the tricky part is to notice that,
G(n)=G(n-1)+S(n)
where S(n) is the summation of gcd(i,n) where i runs from 1 to n-1. So, if we can find S(n) fast enough, we can solve the problem taking cumulative sum.
Next, we apply the same lemma as before. For a particular i, how many times does gcd(i,n) occurs? Since gcd(i,n)=d is a divisor of n, then d would occur Phi(n/d) times in the sum S(n). Thus, S(n) is the summation d*Phi(n/d) where d is any divisor of n. In this problem, you need to store the values of Phi in an array while running the Sieve.
By the way, we can prove easily that, sum of Phi(d) = n where d is a divisor of n. So, if x >= n, in the problem Best Friend, the answer would be just "n". O(1) solution!! To sense this, try according to the previous lemma's proof.
Try them. Happy coding!!
Can anybody help me with "Best friend" problem?
I have WA and don't know how to deal with it.
My solution
I calculate Euler function of phi(n / d) for every divisor d of n and then use cumulative sums + binary search.
Stress test doesn't find any errors. Can you help me please?
I am analyzing the code. BTW, I forgot to mention one fact. Read the last part of the post again, please.
I think you are having overflow in go function while finding Phi(n/d). To avoid overflow, I find phi in the following way: First I divide n by the prime and then multiply it by (p-1). Otherwise n*(p-1) may overflow long long. And the input file contains all type of inputs to not let you get an acc easily. But I am not sure, your divisor finding using recursion may be faulty. BTW, you can use sqrt(n) algorithm to find all the divisors. You won't have TLE. I suggest you better use this than recursion. And then find the phi in an array.
I'm not sure that I understood you. As for me, there's no overflow (if there's can you point me the number of line, please?) and I cannot calculate Euler function in O(sqrt(n)) — because I need to do this O(sqrt(n)) times (for each divisor d I need to calculate phi(n/d)). I tried this but it works too long.
Check your inbox.
You can use the property phi(ab)=(phi(a)*phi(b)*d)/phi(d) where d is the gcd of a and b
Nice Article My dear Friend. Maybe you can also add this question here GCD Sum