网站开发的甘特图,鲁山网站建设兼职,在线平面设计兼职,备案老域名1.快速幂
(1)求解问题#xff1a; 给定 n组 ai,bi,pi求 aibi mod pi 的值。 (2)主要思想#xff1a;任何一个数(b)#xff0c;可以被 n 个 2k 相加获得。 即 b 2k1 2k2 2k3 … 2logb。
快速幂模板#xff1a;
typedef long long LL;LL qmi(int a,int b,int p){LL re…1.快速幂
(1)求解问题 给定 n组 ai,bi,pi求 aibi mod pi 的值。 (2)主要思想任何一个数(b)可以被 n 个 2k 相加获得。 即 b 2k1 2k2 2k3 … 2logb。
快速幂模板
typedef long long LL;LL qmi(int a,int b,int p){LL res 1;while(b){if(b 1) res res * a % p;a a * (LL)a % p;b 1;}return res;
}逆元
1求解问题对于a / b mod p的值 将除法改为乘法 例如 求 (A / B) %p 在B的值非常大的情况下B作为除数极有可能会爆精度除数不能太大所以我们可以把他转化为乘法来解决 2主要思想 费马小定理对于bp-1mod p 1 恒成立。且 逆元b * b-1 1 (mod p) 所以 b 的逆元 b-1 为 bp-2. 可以用快速幂来求
b^-1^ qmi(b,p-2,p);
