### baowilliam's blog

By baowilliam, history, 2 months ago,

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

• +26

 » 2 months ago, # |   0 Auto comment: topic has been updated by baowilliam (previous revision, new revision, compare).
 » 2 months ago, # |   0 Auto comment: topic has been updated by baowilliam (previous revision, new revision, compare).
 » 2 months ago, # |   +5 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 :)
•  » » 2 months ago, # ^ |   +19 thank you!!!, btw how about the case when k is not co-prime with 2 :(
•  » » 2 months ago, # ^ |   0 from where can we study all this?
•  » » » 2 months ago, # ^ |   0 +1
•  » » » 2 months ago, # ^ |   -10 I learned it from the website: https://www.geeksforgeeks.org/
•  » » » » 2 months ago, # ^ |   0 can you share the link of the article where you read it?
•  » » » » » 2 months ago, # ^ |   0 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/
•  » » » » » » 2 months ago, # ^ |   0 Thanks bro
 » 2 months ago, # | ← Rev. 7 →   0 Deleted.
 » 2 months ago, # | ← Rev. 6 →   +2 You can use the extension of Fermat's little theorem, the so-called Euler's Theorem. According to the theorem, the following is true. $n^{\phi(m)} \equiv 1\pmod m$Therefore the following is also true: $n^k\equiv n^{k\bmod\phi(m)}\pmod m$These problems, in CP and MO, are called Power Towers. They usually ask for a very big power modulo a composite number like these. $a_0^{a_1^{a_2^{a_3^{a_4^{{\text{(omitted some powers)}}^{a_n}}}}}} \bmod m$(btw how do I use antidiagonal dots on LaTeX? this long text looks ugly as heck)
•  » » 2 months ago, # ^ |   +11 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?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +12 Oops, I forgot to also explain this, the following is true regardless of whether the two are coprime or not. $x^{n}\equiv x^{\phi(m)+[n \bmod \phi(m)]} \mod m$UPD: LipArcanjo is correct, the exponent needs to exceed log2(m) for this
 » 2 months ago, # | ← Rev. 2 →   0 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.
 » 2 months ago, # |   +8 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$.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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 #include #include using namespace std; using ll=long long; long long phi(int N){ long long ans = N; for (int i = 2; i*i <= N; i++){ if (N % i == 0){ while (N % i == 0) N/=i; ans -= ans/i; } } if (N > 1) ans -= ans/N; return ans; } ll binpow(ll b, ll p, ll m){ ll ans = 1; while (p > 0){ if (p&1) ans = ans * b % m; b = b * b % m; p >>= 1 ; } return ans % m; } ll comp_22np1_modm(ll n,ll m) { if(n>=log2(log2(m))) //lazy way to do 2^n>=log2(m) { ll p=phi(m); return (binpow(2,p+binpow(2,n,p),m)+1)%m; } return (binpow(2,1<>n>>k; cout<
 » 2 months ago, # |   0 Finally, I have done for this problem.! Thank you guys all for help!!!!!
•  » » 2 months ago, # ^ |   0 it so hard for me to understand, can u help me ?? :3