- "Who am I" Movie

Have you seen this movie ? The movie is about a hacker team that wants to get the attention of MRX biggest hacker ... OK OK I don't want to ruin the movie ... I suggest that you watch it if you are interested in mysterious movies. It's IMDB score is 7.6 .

I watched the movie twice later and I really enjoyed it. Tonight because we were bored , decided to watch a movie and since "Sakene Tabaghe ye Vasat" couldn't attract us ( maybe it is for artists ) , I suggested to watch this movie again.


- Another usage of Fermat's Little Theorem

One of the well-known Fermat's Little Theorem applications is finding inversion of a number according to this relation when p is a prime : a^(p-2) ~ 1/a

Today I want to tell another usage of it according to : a^(p-1) ~ 1 [ original relation ]


Problem : we get numbers x and n and then n numbers a1,a2,...,an and we want to find x^(a1*a2*...*an) modulo 1e9 + 7. ( 1 <= n <= 1e5 , 2 <= x , ai <= 1e9 )

Solution : If there was + instead of * in the formula , then we could simply calculate x^a1 * x^a2 * ... but they are * and the multiplied number can be so huge. so what we can do ?


According to this formula x^(p-1) ~ 1 [ modulo prime p ] and knowing that here p = 1e9 + 7 , Then we conclude that --> x^y ~ x^(y%(p-1)) [ modulo prime p ]

That's it! For solving the problem we just need to find x^( (a1*a2*...*an) % (p-1) ). And it is solvable in logarithmic time with Binary Exponentiation.


As a training you can try this problem : 615D. Multipliers