baowilliam's blog

By baowilliam, history, 2 months ago, In English

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

 
 
 
 
  • Vote: I like it
  • +26
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by baowilliam (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by baowilliam (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

Deleted.

»
2 months ago, # |
Rev. 6   Vote: I like it +2 Vote: I do not like it

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, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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   Vote: I like it +12 Vote: I do not like it

      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   Vote: I like it 0 Vote: I do not like it

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 message
»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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<iostream>
    #include<cmath>
    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,m)+1)%m;//n<log2(log2(m)) is very small
    }
    
    int main()
    {
     ll n,k;cin>>n>>k;
     cout<<comp_22np1_modm(n,k);
    }
    

    Thank you!! and waiting for you reply!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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