2019 计蒜之道 第三场 D（找规律+欧拉降幂）

题目链接：https://nanti.jisuanke.com/t/38352

先找出规律

由于n非常大，因此我们需要用到欧拉降幂

由于1e9+7为素数，故phi(1e9+7)=1e9+6

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int mod=1e9+7,amod=1e9+6;
char a[100010];
LL quick(LL a,LL b)
{
    LL res=1;
    while(b)
    {
        if(b&1)res=(res*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return res;
}
int main()
{
    while(~scanf("%s",a))
    {
        if(a[0]=='0')break;
        LL s=0;
        for(int i=0;i<strlen(a);i++)
        {
            int t=a[i]-'0';
            s=((s*10)%amod+t%amod)%amod;
        }
        LL sum=(quick(4,s-1)+quick(2,s-1))%mod;
        printf("%lld
",sum);
    }
    return 0;
}