Math solusion based on Euler's theorem, power called only ONCE, C++/Java/1-line-Python


  • 45

    1337 only has two divisors 7 and 191 exclusive 1 and itself, so judge if a has a divisor of 7 or 191, and note that 7 and 191 are prime numbers, phi of them is itself - 1, then we can use the Euler's theorem, see it on wiki https://en.wikipedia.org/wiki/Euler's_theorem, it's just Fermat's little theorem if the mod n is prime.

    see how 1140 is calculated out:
    phi(1337) = phi(7) * phi(191) = 6 * 190 = 1140

    optimized solution update at 2016-7-12

    Today, seeing @myanonymos 's comments, and I find several days ago I AC it just by fortunate coincidence, it's not the best solution. now I get a better idea.

    (1) Firstly, if a has both divisor 7 and 191, that's a % 1337 == 0, answer is 0.
    (2) Then if a has neither divisor 7 nor 191, that's a and 1337 are coprime, so ab % 1337 = ab % phi(1337) % 1337 = ab % 1140 % 1337.

    (3) Finally, a could has either divisor 7 or 191, that's similar.
    Let it be 7 for example.
    Let a = 7nx
    and let b = 1140p + q, where 0 < q <= 1140
    then:

    ab % 1337
    = ((7nx)b) % 1337
    = (7nbxb) % 1337
    = ( (7nb % 1337) * (xb % 1337) ) % 1337
    = ( (71140np + nq % 1337) * (x1140p + q % 1337) ) % 1337

    now note x and 1337 are coprime, so

    = ( (71140np + nq % 1337) * (xq % 1337) ) % 1337
    = ( 7 * (71140np + nq - 1 % 191) * (xq % 1337) ) % 1337

    note 7 and 191 are coprime too, and 1140 is a multiple of 190, where 190 = phi(191). What's more we should assure that q != 0, if b % 1140== 0, then let b = 1140. so

    = ( 7 * (7nq - 1 % 191) * (xq % 1337) ) % 1337
    = ( (7nq % 1337) * (xq % 1337) ) % 1337
    = (7nqxq) % 1337
    = ((7nx)q) % 1337
    = (aq) % 1337

    now you see condition (2) and (3) can be merged as one solution, if you take care of when b % 1440 == 0, and let b += 1140. Actually (1) can be merged too, but not efficient.

    new code:
    C++:

    int superPow(int a, vector<int>& b) {
        if (a % 1337 == 0) return 0; // this line could also be removed
        int p = 0;
        for (int i : b) p = (p * 10 + i) % 1140;
        if (p == 0) p += 1140;
        return power(a, p, 1337);
    }
    int power(int x, int n, int mod) {
        int ret = 1;
        for (x %= mod; n; x = x * x % mod, n >>= 1) if (n & 1) ret = ret * x % mod;
        return ret;
    }
    

    java:

    public int superPow(int a, int[] b) {
        if (a % 1337 == 0) return 0;
        int p = 0;
        for (int i : b) p = (p * 10 + i) % 1140;
        if (p == 0) p += 1440;
        return power(a, p, 1337);
    }
    public int power(int a, int n, int mod) {
        a %= mod;
        int ret = 1;
        while (n != 0) {
            if ((n & 1) != 0) ret = ret * a % mod;
            a = a * a % mod;
            n >>= 1;
        }
        return ret;
    }
    

    Actually, if p == 0 or not, we can always let p += 1140, it doesn't matter.
    one line python:

    def superPow(self, a, b):
        return 0 if a % 1337 == 0 else pow(a, reduce(lambda x, y: (x * 10 + y) % 1140, b) + 1140, 1337)
    

    will this be the best solution?

    p.s.
    I have testcases that the system missed
    574
    [1,1,4,0]

    764
    [1,1,4,0]
    in this case if I remove this line of code if (p == 0) p += 1140;, it will get wrong answer, but also can get AC on OJ.

    and I found thar 574 * 574 % 1337 = 574, 764 * 764 % 1337 = 764, how interesting!


  • 2

    another shorter but slower solution

    int superPow(int a, vector<int>& b) {
        const int mod = 1337;
        int ret = 1;
        for (int i : b)  ret = power(ret, 10, mod) * power(a, i, mod) % mod;
        return ret;
    }
    int power(int x, int n, int mod) {
        x %= mod;
        int ret = 1;
        while (n) {
            if (n & 1) ret = ret * x % mod;
            x = x * x % mod;
            n >>= 1;
        }
        return ret;
    }

  • 2
    M

    omg...
    This is so much beyond what I can understand. I did tried my best though.


  • 0
    M

    @ShuangquanLi
    Could you explain a little bit about how the power function works? I tried with paper and pen. The answers are correct...but mysteriously. Thank you!


  • 0
    M
    This post is deleted!

  • 0
    C
    This post is deleted!

  • 0
    M

    I understood now! Thank you so much for sharing your genius solution! This solution uses math intelligently and circumvented all the possibilities of having too big numbers! I vote for you!


  • 0

    @myanonymos hey, bro! I have got a better solution and made explanation, do you really understand it before? Even myself feel that is weird when I wanna explain it to you.


  • 1

  • 0
    This post is deleted!

  • 1

    @ctzsm Very nice proof! Thank you, my countryman!

    here give out a summary.

    to calc ab%n

    1. if b <= φ(n), use quick power
    2. if b > φ(n), ab ≡ ab % φ(n) + φ(n) %n

    In this problem, n = 1337 = 7 * 191, where the exponent of 7 and 191 are both 1, so for any a, if a % 1337 != 0, aφ(1337) % 1337 = 1, if a % 1337 == 0, aφ(1337) % 1337 = 0.
    Thus we can always calc ab % 1337 = ab + φ(1337) % 1337, it is the candition 2.

    Finally the solution is:
    ab%1337 = ab + φ(1337) % 1337 = a(b + φ(1337)) % φ(1337) + φ(1337) % 1337 = ab % φ(1337) + φ(1337) % 1337


  • 0
    M

    @ShuangquanLi I did understand it and I read your summaries too. Thank you very much! But did you say you got better solutions than this? What is that?


  • 0

    @myanonymos Ok, sorry I made mistakes. Leave me alone.


  • 1
    W
    return 0 if a%1337==0 else pow(a%1337, reduce(lambda x,y:(x*10+y)%1140, b)+1140, 1337)
    

    may be more better.


  • 0

    @Windy-Ground Yeah, agree with you.Thanks


  • 0
    G

    wo ri. if someone wants me come up with this solution, I will definitely ger pee la.


  • 0

    Cool solution...take me quite a time to understand, thanks for sharing!
    However, it's not a common solution and only works for 1337. Once the number changes you'll have to recalculate.


  • 0
    A
    This post is deleted!

  • 0
    R

    Great!
    A typo in python version 1440 should be 1140.
    @administrators @contributors @Global-Moderators
    There is a kind of missing testcases!


  • 1
    V

    though my undergraduate majored in mathematics and learned abstract algebra it still took me 3 hours to understand how it works. Genius.
    (zhong wen ban: gei da shen ni gui xia le ....)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.