建设彩票网站需要哪些要求,城乡与住房建设厅网站首页,微信营销成,如何自己创建网页快速幂模简述师从普通思路缺陷一#xff1a;溢出缺陷二#xff1a;运算次数多二分化快速幂模简述
计算 ana^nanmod p
师从
本篇是观Vita君算法视频后总结#xff0c;他是bilibili一位小up主#xff1a;小学生Vita君 正所谓“生乎吾后#xff0c;其闻道也亦先乎吾#…
快速幂模简述师从普通思路缺陷一溢出缺陷二运算次数多二分化快速幂模简述
计算 ana^nanmod p
师从
本篇是观Vita君算法视频后总结他是bilibili一位小up主小学生Vita君 正所谓“生乎吾后其闻道也亦先乎吾吾从而师之”诚然如此。 【算法小知识】如何计算快速幂上
普通思路
(aaaaaa……aaa) % p
缺陷一溢出
ana^nan可能会溢出
解决方案边乘边模 基于 (a*b) mod p (a mod p)(b mod p) 成立 (aaaa……)(a%p)(a%p)(a%p)(a%p)……
缺陷二运算次数多
当n较大时运算次数很大速度慢
解决方案二分化思想 ana^nanan2a^\frac{n}{2}a2nan2a^\frac{n}{2}a2n an2a^\frac{n}{2}a2nan4a^\frac{n}{4}a4nan4a^\frac{n}{4}a4n …… (当指数为奇数时需额外乘a 将时间复杂度O(n) → O(logn)
二分化快速幂模
#includeiostream
using namespace std;typedef unsigned long long ull;
ull binpow(ull a, ull n, ull p)
{if (n 0) return 1;a % p;ull c binpow(a, n / 2, p);if (n % 2 ! 0) return c * c % p *( a % p );return c * c % p;
}
int main()
{ull a, n, p;cin a n p;cout binpow(a, n, p) % pendl;
}非递归
ull binpow(ull a, ull n, ull p)
{ull prod 1;while(n 0){if (n 1) prod prod * a % p;a * a % p;n 1;}return prod;
}
