题解 P1226 【【模板】快速幂||取余运算】

· · 题解

第一篇题解

重点提醒：

不取模，通不过。

不然只能得40；

方法1： 高精度？

大概是 $4\times10^{2389}

想累死自己的就敲去。

方法2： 快速幂+取模

众所周知，快速幂的时间复杂度为O(log_2 n)

这4\times10^{2389}怎么办？

取模！

代码应该都懂

普通不取模：40

#include <bits/stdc++.h>
using namespace std;
long long a,b,c;
long long fpow(long long a,long long b)
{
    long long ans=1;
    if(b==0)return 1;
    if(b==1)return a;
    if(b%2==0)
    {
        ans=fpow(a,b/2);
        ans=ans*ans;
    }
    else
    {
        b--;
        ans=fpow(a,b/2);
        ans=ans*ans;
        ans=a*ans;
    }
    return ans;
}
int main()
{

    cin>>a>>b>>c;
    cout<<a<<'^'<<b<<" mod "<<c<<'='<<fpow(a,b)%c<<endl;
    return 0;
}

取模：100

#include <bits/stdc++.h>
using namespace std;
long long a,b,c;
long long fpow(long long a,long long b)
{
    long long ans=1;
    if(b==0)return 1;
    if(b==1)return a;
    if(b%2==0)
    {
        ans=fpow(a,b/2)%c;
        ans=ans*ans%c;
    }
    else
    {
        b--;
        ans=fpow(a,b/2)%c;
        ans=ans*ans%c;
        ans=a*ans%c;
    }
    return ans;
}
int main()
{

    cin>>a>>b>>c;
    cout<<a<<'^'<<b<<" mod "<<c<<'='<<fpow(a,b)%c<<endl;
    return 0;
}

细节问题，大佬勿喷。

求管理员过。