Raising Modulo Numbers(ZOJ 2150)

这题其实就是快速求一个高次幂的模。

这是题目的答案

#include<iostream>

#include<cmath>

using namespace std;

int a[];

int b[];

int mod(int a, int b, int c)

{

    int z = ;

    while(b)

    {

        if(b%)

            z = (z*a)%c;

        b/=;

        a = (a*a)%c;

    }

    return z;

}

int main()

{

    int T;

    cin>>T;

    while(T--)

    {

        int M;

        int H;

        cin>>M>>H;

        for(int i=; i<H; i++)

        {

            cin>>a[i]>>b[i];

        }

        int t =;

        int mode = ;

        while(t<H)

        {

            int tem0 = a[t]%M;

            mode = (mod(tem0,b[t],M) + mode)%M;

            t++;

        }

        cout<<mode<<endl;

    }

}

只分析求幂—模的那个函数，先举例吧（a a a a a a a a a a）这是b个a （b =10），通过z来记录二分时多出来的一个a，每次二分后用a来代替a*a，这样就得到了缩小规模的结果。最后肯定是b=1，所以这时只需用现在的a与z结合就是最后的结果了。

int mod(int a, int b, int c)

{

    int z = ;

    while(b)

    {

        if(b%)

            z = (z*a)%c;

        b/=;

        a = (a*a)%c;

    }

    return z;

}

这个函数的写法就是二分法而已，但是刚开始时我写的是这样的

long long F(long long a, long long b, long long m)

{

    if(b==)

        return a%m;

    else if(b%==)

        return (F(a,b/,m)*F(a,b/,m))%m;

    else

        return (F(a,b/,m)*F(a,b/,m)*a%m);

}

这样写的结果是RE，估计是递归太深导致堆栈溢出了，这个写的很差，根本没有起到二分的效果，反而比O(n)还要费时间。

巴特西

Raising Modulo Numbers(ZOJ 2150)

最新文章

热门文章