Q:
Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.
Example1:
a = 2 b = [3] Result: 8
Example2:
a = 2 b = [1,0] Result: 1024
A:
就是记录下每一位的模,然后逐步相乘即可public class Solution { public int superPow(int a, int[] b) { if(b.length==0) return 1; int n = b.length; int [] C = new int[ n ]; // 10^i of a/1337 Arrays.fill(C,1); C[n-1] = a % 1337; for(int i =n-2;i>=0;i--){ // for each position , loop 10 times for(int j = 0;j<10;j++){ C[i] = (C[i] * C[i+1]) % 1337; } } int res = 1; for(int i =0;i<n;i++){ for(int j = 0;j<b[i];j++){ res = (res*C[i] ) % 1337; } } return res; } }
No comments:
Post a Comment