20186gdoi13

快速幂

Posted on Edited on In Valine:
Symbols count in article: 477 Reading time ≈ 1 mins.
Template002

例题：LuoguP1226

递归版

1
2
3
4
5
6
7
8
unsigned long long pow(unsigned long long base,unsigned long long power)
  {
    if (power==0) return 1%k;
    if (power==1) return base%k;
    unsigned long long l=pow(base,power/2);
    if (power%2==0) return (l*l)%k;
    else return (((l*l)%k)*base)%k;
  }

循环版

1
2
3
4
5
6
7
8
9
10
11
inline unsigned long long power(unsigned long long base,unsigned long long power)
  {
    unsigned long long res=1;
    while (power>0)
      {
        if (power&1) res=(res*base)%k;
        base=(base*base)%k;
        power>>=1;
      }
    return res;
  }