快速幂

模板 公式

• 快速幂模板

#define LL long long
LL quick(LL x,LL m,LL n)//ans=x^m%n
{
    LL ans=1;
    LL base=x%n;
    while(m)
    {
        if(m&1)
           ans=(ans*base)%n;
        base=(base*base)%n;//算一次模一次
        m>>=1;//右移=/2
    }
    return ans;
}

• HDU-2817
  题意

  输入n，n为测试组数，每组数据输入四个数a,b,c,k。前三个数表示一个序列（等差或等比）,输出该序列的第k项。这个题目数据很大一定要记得取模。千万不要爆了。嘻嘻。

  样例

  Sample Input
  2
  1 2 3 5
  1 2 4 5
  Sample Output
  5
  16

代码

#include<stdio.h>
#define LL long long
LL quick(LL x,LL m,LL n)//ans=x^m%n
{
    LL ans=1;
    LL base=x%n;
    while(m)
    {
        if(m&1)
           ans=(ans*base)%n;
        base=(base*base)%n;//算一次模一次
        m>>=1;//右移=/2
    }
    return ans;
}
int main()
{
    LL n,q,ans,k,a,b,c;
    scanf("%lld",&n);
    while(n--)
    {
        scanf("%lld%lld%lld%lld",&a,&b,&c,&k);
        if(b-a==c-b)
        {
            ans=((a%200907)+((k-1)%200907)*((b-a)%200907));
            printf("%lld\n",ans%200907);
        }
        else
        {
            q=b/a;
            ans=quick(q,k-1,200907);
            printf("%lld\n",((a%200907)*ans)%200907);
        }
    }
     return 0;
}