with $$$(0\leq n\leq 2^{31}-1)$$$ caculate: $$$(2^{2^{n}} + 1)$$$ mod k $$$(1\leq k\leq 10^{6})$$$ i'm doing an exercise on mods for large numbers, i don't know if there is a more efficient solution than using binary exponentiation? Hope to help you, thanks (sorry for my bad english!!!!)

Auto comment: topic has been updated by baowilliam (previous revision, new revision, compare).Auto comment: topic has been updated by baowilliam (previous revision, new revision, compare).Assuming the case when $$$k$$$ is a prime number.

Let, $$${ans = (2^{2^n} + 1)}$$$ mod $$$k$$$

let's modify a little bit

$$${2^{2^n}}$$$ mod $$${k = (ans + k - 1)}$$$ mod $$$k$$$ $$${ = x}$$$

Using Fermat Little Theorem, let $$${p = (2 ^ n)}$$$ mod $$$(k - 1)$$$

so, $$${x = (2 ^ p)}$$$ mod $$$k$$$.

so you may easily calculate $$$p$$$ first then calculate $$$x$$$ then can form the $$$ans$$$ easily :)

thank you!!!, btw how about the case when k is not co-prime with 2 :(

from where can we study all this?

+1

I learned it from the website: https://www.geeksforgeeks.org/

can you share the link of the article where you read it?

Sure: Here are 2 links that I learned to solve this prolem: https://www.geeksforgeeks.org/fermats-little-theorem/ https://www.geeksforgeeks.org/eulers-totient-function/

Thanks bro

Deleted.

You can use the extension of Fermat's little theorem, the so-called

Euler's Theorem. According to the theorem, the following is true.Therefore the following is also true:

These problems, in CP and MO, are called

Power Towers. They usually ask for a very big power modulo a composite number like these.(btw how do I use antidiagonal dots on LaTeX? this long text looks ugly as heck)

but we just can use fermat's little theorem if and only if (n and m) are co-prime, <=> 2 and k are co-prime, and I really don't know the case when 2 and k aren't co-prime :(, can you explain a little bit?

Oops, I forgot to also explain this, the following is true regardless of whether the two are coprime or not.

UPD: LipArcanjo is correct, the exponent needs to exceed log2(m) for this

Edit: as of chromate00's reply/explanation, I've realized this solution is bad and ugly. One should refer to his messages for a better solution.

Previous messageIf n <= 5, $$$2^n <= 32$$$, so you can compute the result in a long long with no special tricks.

Now, for n >= 6...

Let

`exp2`

be the exponent of 2 in the prime decomposition of k. Let`m`

be $$$k / 2^{exp2}$$$.We now have that 2 and m are coprime. Perfect!

Now, we can use chromate00's neat technique as such:

We know that $$$2^{2^{n}-exp2} \equiv 2^{(2^{n}-exp2) \ mod \ \phi(m)} \ (mod \ m)$$$.

$$$(2^{n}-exp2) \ mod \ \phi(m)$$$ can easily be calculated (totient function computation, then binary exponentiation and basic modulo subtraction). Since the result to this mod is <= m, we can use binary exponentiation again to find $$$2^{(2^{n}-exp2) \ mod \ \phi(m)} \ (mod \ m)$$$, which is equal to $$$2^{2^{n}-exp2} \ (mod \ m)$$$.

Let this result be x. We have that $$$2^{2^{n}-exp2} \ \equiv \ x \ (mod \ m)$$$. We can multiply this by $$$2^{exp2}$$$, thus getting: $$$2^{2^{n}} \ \equiv \ x * 2^{exp2} \ (mod \ k)$$$ (remember that

`m`

is $$$k / 2^{exp2}$$$). Finally, $$$2^{2^{n}}+1 \ \equiv \ x * 2^{exp2}+1 \ (mod \ k)$$$.Do a mod on $$$x * 2^{exp2}+1$$$ and that's your answer!

Let me know if there is anything you don't understand.

The statement:

$$$n^e \ mod \ m = n^{\phi(m) + e \ mod \ \phi(m)} \ mod \ m$$$

is true for all $$$n ,m,$$$ and $$$e \geq log_2(m)$$$.

Source: https://nordic.icpc.io/ncpc2016/ncpc2016slides.pdf Problem E.

So If $$$n$$$ is greater or equal then $$$log_2(k)$$$, you use the equation, if not, you can compute $$$2^n$$$.

Yeah, base on @chromate00's code and I just modify a littlebit. But the solution still not work and I got WA for many times :(. Can you point out what's wrong with my code? :(. Thank you!. Note: It's Problem F from: https://codeforces.com/gym/100975/attachments

Thank you!! and waiting for you reply!

Finally, I have done for this problem.! Thank you guys all for help!!!!!

it so hard for me to understand, can u help me ?? :3