快速幂
- (a + b) % p = (a % p + b % p) % p
- (a - b) % p = (a % p - b % p ) % p
- (a * b) % p = (a % p * b % p) % p
但是第三个公式效率当然是非常的低下
于是我们可以使用快速幂算法
快速幂算法核心
快速幂算法的核心思想就是每一步都把指数分成两半
$3^{10}$ = $3$ * $3$ * $3$ * $3$ * $3$ * $3$ * $3$ * $3$ * $3$ * $3$
–>尽量想办法把指数变小来,这里的指数为10
$3^{10}$ = $9^{5}$
–>此时指数由10缩减一半变成了5
–>在C语言中,power%2==1可以用更快的“位运算”来代替,例如:power&1。
快速幂模板:
if (power & 1) {//此处等价于if(power%2==1)
因为如果power为偶数,则其二进制表示的最后一位一定是0;
如果power是奇数,则其二进制表示的最后一位一定是1
long long fastPower(long long base, long long power) {
long long result = 1;
while (power > 0) {
if (power & 1) {//此处等价于if(power%2==1)
result = result * base % mod;
}
power >>= 1;//此处等价于power=power/2
base = (base * base) % mod;
}
return result;
}
题目练习
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;
ll qpow(ll x, ll y){
ll res = 1;
while(y){
if(y & 1) res = (res * x) % mod;
y >>= 1;
x = (x * x) % mod;
}
return res;
}
ll n, m;
int main(){
cin >> n >> m;
ll ans = 0;
for(ll i = n; i <= m; ++i){
ans = (ans + qpow(4LL, i)) % mod;
}
cout << ans << "\n";
}
补充例题:
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int mod=998244353;
typedef long long ll;
int n,m;
int a[N];
int main(){
scanf("%d", &n);
for(int i=0;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);
while(m--){
ll x,res=1,ans=0;
scanf("%d",&x);
for(int i=0;i<=n;i++){
ans = (ans+a[i]*res) % mod;
res = res * x % mod;
}
printf("%lld ",ans);
}
return 0;
}