# Quick Pow

``````例如 231 % 3 = 2

``````

``````O(logn)
``````

## Solution

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

an = an/2⋅an/2 = an/4⋅an/4⋅an/4⋅an/4 = ...

## Code

``````class Solution {
/*
* @param a, b, n: 32bit integers
* @return: An integer
*/
public int fastPower(int a, int b, int n) {
if (n == 1) {
return a % b;
} else if (n == 0) {
return 1 % b;
} else if (n < 0) {
return -1;
}

// (a * b) % p = ((a % p) * (b % p)) % p
// use long to prevent overflow
long product = fastPower(a, b, n / 2);
product = (product * product) % b;
if (n % 2 == 1) {
product = (product * a) % b;
}

// cast long to int
return (int) product;
}
};

``````
{"ft_lang_label":"__label__zh","ft_lang_prob":0.69976294,"math_prob":0.99745536,"size":1156,"snap":"2023-40-2023-50","text_gpt3_token_len":708,"char_repetition_ratio":0.105902776,"word_repetition_ratio":0.119266056,"special_character_ratio":0.39532873,"punctuation_ratio":0.13537118,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99904037,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-03T17:27:29Z\",\"WARC-Record-ID\":\"<urn:uuid:92fdfb8e-94ec-4570-bab2-64e150dea5c8>\",\"Content-Length\":\"115421\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:e07c88cf-838b-4768-963f-3548bc645a71>\",\"WARC-Concurrent-To\":\"<urn:uuid:216ed6ae-1b9b-46cf-95cb-9f80a03dd321>\",\"WARC-IP-Address\":\"120.24.170.254\",\"WARC-Target-URI\":\"https://wdxtub.com/interview/14520603231831.html\",\"WARC-Payload-Digest\":\"sha1:LFU2F3PIKBZD6DVKNGSZJHLHOFBILZW3\",\"WARC-Block-Digest\":\"sha1:DILR4FS5TY36MPRREZEPCELHQ74I57UJ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100508.42_warc_CC-MAIN-20231203161435-20231203191435-00634.warc.gz\"}"}