I can't remember the name of the problem. But here is the problem description.

Given a positive integers n <= 10^5, a, b. Find a^{F(n)*b} mod M where

F(n)=C(n,0)^2+C(n,1)^2+...+C(n,n)^2

where C(n,k) is the number of ways to choose k distinct objects from n distinct objects and M=10^9+7.

First, we need to find F(n) in a closed form in order to avoid TLE. Because generating C(n,k) needs O(n) time.

We can write the sum as this:

F(n)=C(n,0)*C(n,n)+C(n,1)*C(n,n-1)+...+C(n,n)*C(n,0)

because C(n,k)=C(n,n-k) as we know. What does C(n,i)*C(n,n-i) mean? Think clearly. It means you have to choose i persons from n in C(n,i) ways and once again C(n,n-i) means you can choose n-i persons from n persons. Together what can we say?

If there are 2n persons in a pool, in how many ways can you choose n of them? In C(2n, n) ways. On the other hand, think this way. Divide them into two parts, each having n persons. Now, if you choose i persons from the n of the first pool, you have to choose n-i others from the second. Thus together you can have C(n,i)*C(n,n-i) choices. Since i can run from 0 to n, we have that

C(n,0)*C(n,n)+C(n,1)*C(n,n-1)+...+C(n,n)*C(n,0) = C(2n, n)

Thus, F(n)=C(2n,n). Now we have narrowed it down. We only need a^{C(2n,n)*b}%M.

We can use Fermat's Little Theorem. You have to find the remainder of C(2n,n)*b upon division by M-1. But how would you calculate C(2n,n)? You can try with the primes less than or equal to n and how many times they occur(You have to use Legendre's Theorem).

But I already got TLE using this method. So we need another idea. I don't know what the author's solution is, but here is what I did.

From previous experience, I knew that for M=10^9+7, N=(M-1)/2=5*10^8+3 is a prime. Also, from the identity,

k*C(n,k) = n*C(n-1,k-1)

we need that, C(2n,n)=2C(2n-1,n-1)%2N with N a prime. Then

C(2n,n)%2n=2*C(2n-1,n-1)%2N

We can invoke Extended Euclidean Algorithm

C(n,k)=n!/(k!*(n-k)!)

So if 2n is co-prime with k! and (n-k)!, we can find the modular inverses of them modulo 2n. There lies the main problem. 2n is not co-prime with k! of (n-k)!. They share 2 as a common factor. If we can rule out 2, then we can find the remainder with Extended_Euclid. The previous identity lets us use this fact.

We shall find the remainder of C(2n-1,n-1) upon division by N. If we find

C(2n-1,n-1)%N=r

then C(2n,n)%2n=2*r%(2N). Store the values of n! modulo M upto n=10^5. Then use EEA to find their modular inverses. Then use fast modular exponentiation.

Once one of my friend told that, he heard from someone else-"Every problem from SpOJ needs a different algorithm to get an ac." I guess he is right!!

The following problems involve a sum of gcd. And this particular type of ideas are needed in some other problems too.

GCD

GCD Extreme I

GCD Extreme II

Best Friend

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!!

We use Eratosthenes sieve for prime factorization, storing the primes in an array. But for that, we need to find the primes less than or equal to sqrt(n) which divide n. There are about n/log(n) primes less than or equal to n. So, the complexity is roughly sqrt(n)/log(sqrt(n))*log(n). But if n is asked to be factorized completely where n is within the Sieve range, then we can factorize n is log(n) complexity. And the trick is fairly small. Observe, that, we don't need to run a whole sqrt(n) loop for finding the prime divisors. Instead, we can even store them when n is in the range, say n<= 10^7. But the tricky part is not to store all the prime divisors of n. Let's see the following simulation. Take n = 60. We want to factorize n. We will store the smallest prime factors only. This does the trick. If n is composite, then it has such a prime factor, otherwise n is a prime and then the n itself is the smallest prime factor. It is obvious, for any even number n, sp(n)=2. Therefore, we only need to store these primes for odd n only. If we denote the smallest prime factor of n by sp(n), for odd 2 <= n <= 30, we get the following list.

sp(2n)=2, sp(3)=3, sp(5)=5, sp(7)=7, sp(9)=3, sp(11)=11, sp(13)=13, sp(15)=3, sp(17)=17, sp(19)=19, sp(21)=3, sp(23)=23, sp(25)=5, sp(27)=3, sp(29)=29.

Then the factorization is very simple. The optimization is needed only once, when the Sieve() function runs.

bool v[MAX];
int len, sp[MAX];

void Sieve(){
	for (int i = 2; i < MAX; i += 2)	sp[i] = 2;//even numbers have smallest prime factor 2
	for (lli i = 3; i < MAX; i += 2){
		if (!v[i]){
			sp[i] = i;
			for (lli j = i; (j*i) < MAX; j += 2){
				if (!v[j*i])	v[j*i] = true, sp[j*i] = i;
			}
		}
	}
}

int main(){
	Sieve();
	for (int i = 0; i < 50; i++)	cout << sp[i] << endl;
	
    return 0;
}

Now, notice the difference between the usual prime factorization and this one! The only problem is, you can't use this for n large enough in int range. Still, it seems nice to me and pleasured me when I first found this.