P1405 苦恼的小明

· · 题解

P1405 苦恼的小明

题目传送门

前置知识

不要脸的安利自己的博客

解法

前几个点就是裸的快速幂。

后几个点的指数会很大，直接快速幂不能得到正解，所以要用到欧拉定理的推论。

首先我们要知道幂运算的次序，即先计算指数部分，所以我们要用到递归。

关于我是个蒟蒻这件事

扩展欧拉定理内容：

\begin{cases} a^{b\bmod \varphi(n)}&\pmod n,\gcd(a,n)=1\\ a^b&\pmod n,\gcd(a,n)\ne1,b<\varphi(n)\\ a^{(b\bmod\varphi(n))+\varphi(n)}&\pmod n,\gcd(a,n)\ne1,b\ge\varphi(n)\\ \end{cases}

那么在计算过程中我们就紧贴定理，分类讨论：

int js(int i,int p)
{//计算
    if(i==n)return a[n]%=p;//递归边界
    int phi=_phi(p);//计算欧拉函数值
    int nex=js(i+1,phi);//计算指数的值
    if(gcd(a[i],p)==1)return a[i]=ksm(a[i],nex,p);//互质时直接用欧拉定理
    else
    {
        if(a[i+1]<phi)return a[i]=ksm(a[i],a[i+1],p);//指数较小，不用欧拉定理直接运算
        return a[i]=ksm(a[i],nex+phi,p);//指数大，用扩展欧拉定理进行运算
    }
}

主要函数就这一点儿，关于欧拉函数的求值和欧拉定理及扩展欧拉定理的证明我的博文中也写的比较清楚。

主要是懒

Code:

#include<cstdio>
#define int long long
using namespace std;
int re()
{
    int s=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        s=s*10+ch-48,ch=getchar();
    return s*f;
}
void wr(int s)
{
    if(s<0)putchar('-'),s=-s;
    if(s>9)wr(s/10);
    putchar(s%10+48);
}
const int inf=1234568,mod=1e4+7;
int n,a[inf];
int _phi(int n)
{
    int ans=n;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}
int ksm(int a,int b,int p)
{
    int ans=1;
    while(b)
    {
        if(b&1)ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}
int gcd(int x,int y)
{
    while(y^=x^=y^=x%=y);
    return x;
}
int js(int i,int p)
{
    if(i==n)return a[n]%=p;
    int phi=_phi(p),nex=js(i+1,phi);
    if(gcd(a[i],p)==1)return a[i]=ksm(a[i],nex,p);
    else
    {
        if(a[i+1]<phi)return a[i]=ksm(a[i],a[i+1],p);
        return a[i]=ksm(a[i],nex+phi,p);
    }
}
int main()
{
    n=re();
    for(int i=1;i<=n;i++)
        a[i]=re();
    wr(js(1,mod));
    return 0;
}

建议先做 P5091 【模板】扩展欧拉定理 以熟悉扩展欧拉定理。