Applese 涂颜色（欧拉降幂）

链接：https://ac.nowcoder.com/acm/contest/330/E

来源：牛客网

题目描述

精通程序设计的 Applese 叕写了一个游戏。

在这个游戏中，有一个 n 行 m 列的方阵。现在它要为这个方阵涂上黑白两种颜色。规定左右相邻两格的颜色不能相同。请你帮它统计一下有多少种涂色的方法。由于答案很大，你需要将答案对 109+7109+7 取模。

输入描述:

仅一行两个正整数 n, m，表示方阵的大小。

输出描述:

输出一个正整数，表示方案数对 109+7109+7 取模。

示例1

输入

复制

1 1

输出

复制

示例2

输入

复制

2 2

输出

复制

备注:

1≤n,m≤10^100000

思路：思路很简单，就是2的n次方膜1e9+7，但是我们有个问题，就是数据的问题，10^100000，数据太大，我们就可以用欧拉降幂，基本板子题欧拉降幂

代码：

#include <bits/stdc++.h>

#define ll long long int

#define mod 100000007

using namespace std;

char a[100005];

char b[100005];

ll x,z=mod;

ll quickpow(ll x,ll y,ll z)

{

    ll ans=1;

    while(y)

    {

        if(y&1)

            ans=ans*x%z;

        x=x*x%z;

        y>>=1;

    }

    return ans;

}

ll phi(ll n)

{

    ll i,rea=n;

    for(i=2;i*i<=n;i++)

    {

        if(n%i==0)

        {

            rea=rea-rea/i;

            while(n%i==0)

                n/=i;

         }

    }

    if(n>1)

        rea=rea-rea/n;

    return rea;

}

int main()

{

    while(scanf("%s %s",a,b)!=EOF)

    {

        ll len=strlen(a);

        ll p=phi(z);

        ll ans=0;

        for(ll i=0;i<len;i++)

            ans=(ans*10+a[i]-'0')%p;

        ans+=p;

        printf("%lld\n",quickpow(2,ans,z));

    }

    return 0;

}

巴特西

Applese 涂颜色（欧拉降幂）

题目描述

输入描述:

输出描述:

输入

输出

输入

输出

备注:

最新文章

热门文章