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

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

• 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;
}``````

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

• @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!

• This post is deleted!

• This post is deleted!

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

• @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.

• This post is deleted!

• @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

• @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?

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

• ``````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.

• @Windy-Ground Yeah, agree with you.Thanks

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

• 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.

• This post is deleted!

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

• 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 ....)

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