欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【计蒜客】2018ICPC焦作赛区网络赛G Give Candies(小费马定理+快速幂)

程序员文章站 2022-03-12 15:36:04
...

题目链接

【计蒜客】2018ICPC焦作赛区网络赛G Give Candies(小费马定理+快速幂)

【题意】

有n个小朋友,排队从老师手中领取n个糖,先到的小朋友先得到若干个糖,直到糖分完,输出有几种分配方式。

 

【解题思路】

规律很好找,就是(2^n-1)%p,但是n太大了,需要用费马小定理转换一下。

费马小定理:若gcd(a,p)=1,那么【计蒜客】2018ICPC焦作赛区网络赛G Give Candies(小费马定理+快速幂)

为了构造一个p-1,使n-1=k(p-1)+m,那么原式即等于2^(n-1)%p=2^k(p-1)%p*2^m%p,即2^(n-1)%p=2^m%p

又因为m=(n-1)%(p-1),所以只需求出m即可。

用字符串输入n,需要做一下预处理,若最后一位>0,直接减1即可,若等于0,需要向高位借位,然后再将字符串转换成整数,边转换边跟p-1取余,最后用快速幂求解。

 

【代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+6;
const int MOD=1e9+7;
char s[100005];
LL quickpow(LL a,LL b)
{
    LL ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ans%MOD;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s);
        if(s=="1")
        {
            printf("1\n");
            continue;
        }
        int l=strlen(s),pos;
        if(s[l-1]>'0')s[l-1]--;
        else
        {
            s[l-1]='9';
            pos=l-2;
            while(s[pos]=='0')
            {
                s[pos]='9';
                pos--;
            }
            s[pos]--;
        }
        LL a=0;
        for(int i=0;i<l;i++)
        {
            a=a*10+(s[i]-'0');
            a=a%mod;
        }
        LL ans=quickpow(2,a);
        printf("%lld\n",ans%MOD);
    }
}