HDU 1852 高速求幂

HDU 1852 快速求幂

题目wa了好多回..悲催...不能直接求逆元来计算，还是要用到数论中的小技巧啊...

贴神牛的题解吧..

// 这题主要求S
// 结论: S = (251^(n+1)-1) * (2^(3n+1)-1) / 250
// 是两个等比数列和相乘
//
// 推理:
// 2008 = 2^3 * 251
// 所以 2008^N 有 3N 个 2 和 N 个251
// 所有仅由2组成的因子有
// 2^0 2^1 2^2 ... 2^(3N)
// 设集合 C = {2^0, 2^1, 2^2 ...,2^(3N)};
// SUM(C) = 2^(3n+1)-1

// 跟251组合产生的因子有
// 251^0 * C
// 251^1 * C
// ...
// 251^N * C

// 所有因子和为:
// S = (251^(n+1)-1))/250 * (2^(3n+1)-1)

// 计算S%K:

// S 很大, 不能保存在普通的数据类型中, 需要直接计算S%K
// 因为S有个分母250, 设 S = X/250
// 则  S%K = (X/250)%K = (X%(250*K))/250
// 变成先求余数再除法的形式

知道了数论中的技巧，不能用你逆元来求哇，因为不满足gcd（250，k ）或者gcd（2，k）不一定是互质的， 代码就不是再是问题了，

#include<stdio.h>
int mult(int a1,int n,int k){
    if(n==0) return 1;
    __int64 b=1,a = a1;
    while(n>1){
        if(n%2==0) {
            a=a*a%k;
            n/=2;
        }
        else {
            b=b*a%k;
            n--;
        }
    }
    return a*b%k;
}
int main(){
    int n,k;
    while(scanf("%d%d",&n,&k),n&&k){
        __int64 a=mult(2,3*n+1,250*k);
        __int64 b=mult(251,n+1,250*k);
        a-- , b--;
        a = ( a*b )%(250*k);
        a /= 250;
        printf("%d\n",mult(2008,a,k));
    }
}