FilesExpand file tree

 master

/

Fast Power.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

executable file

·

62 lines (44 loc) · 1.4 KB

 master

/

Fast Power.java

Copy path

Top

File metadata and controls

• Code
• Blame

executable file

·

62 lines (44 loc) · 1.4 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

M

a^n可以被拆解成(a*a*a*a....*a)， 是乘机形式，而%是可以把每一项都mod一下的。所以就拆开来take mod.

这里用个二分的方法，recursively二分下去，直到n/2为0或者1，然后分别对待.

注意1: 二分后要conquer，乘积可能大于Integer.MAX_VALUE, 所以用个long.

注意2: 要处理n%2==1的情况，二分时候自动省掉了一份，要乘一下。

```

/*

Calculate the a^n % b where a, b and n are all 32bit integers.

Example

For 2^31 % 3 = 2

For 100^1000 % 1000 = 0

Challenge

O(logn)

Tags Expand

Divide and Conquer

*/

/*

Thoughts:

Learn online:

(a * b) % p = (a % p * b % p) % p

Than mean: a ^ n can be divided into a^(n/2) * a^(n/2), that can be used for recursion: divde and conqure.

Note: when n is odd number, it cannot be evenly divided into n/2 and n/2. This case needs special treatment: n = n/2 + n/2 + 1;

*/

class Solution {

/*

* @param a, b, n: 32bit integers

* @return: An integer

*/

public int fastPower(int a, int b, int n) {

if (n == 0) {

return 1 % b;

}

if (n == 1) {

return a % b;

}

long recurPow = fastPower(a, b, n / 2);

recurPow = (recurPow * recurPow) % b;

if (n % 2 == 1) {

recurPow = recurPow * a % b;

}

return (int)recurPow;

}

};

```