问题描述:

简单来说就是让你计算:$$G^{\sum_{d|n} C_n^d} mod 999911659$$

输入:

两个数N、G

输出:

一个数,表示答案除以999911659的余数

思路:

很好的一道题呢,涵盖了大部分数论知识点呢:欧拉定理、中国剩余定理,Lucas定理,组合数取模,逆元….

不过思路不会很复杂。首先指数那么大,肯定不难想到利用欧拉定理将指数缩小,原理可以看这篇文章。所以我们可以将指数变为$\sum_{d|n}C_n^d mod 999911658$,求这个就是求组合数取模,用lucas定理。。。

那么问题来了,我们普通的Lucas定理中模数要求是质数,但这题中模数不是质数,因此我们要用扩展Lucas。首先将模数质因数分解,分解为2,3,4679,35617四个质数。分别在模这四个质数的意义下求出我们要的结果$a_1, a_2, a_3, a_4$。这样答案就可以表示为:
$ans \equiv a_1 (mod 2) $
$ans \equiv a_2 (mod 3) $
$ans \equiv a_3 (mod 4769) $
$ans \equiv a_4 (mod 35617) $
那这样就是中国剩余定理的形式,解出$ans$并利用快速幂$G^{ans}$就好了。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define LL long long
#define mod 999911659
#define MAXN 40005
using namespace std;

const LL prime[5]={0, 2, 3, 4679, 35617};

LL n, g, num[MAXN], fac[MAXN], inv[MAXN];

LL ksm(LL x, LL y, LL p)
{
    LL sum=1;
    while(y)
    {
        if(y&1) sum=(sum*x)%p;
        y>>=1; x=(x*x)%p;
    }
    return sum;
}

LL comb(LL n, LL m, LL p)
{
    if(n<m) return 0;
    return fac[n]*inv[n-m]%p*inv[m]%p;
}

LL lucas(LL n, LL m, LL p)
{
    if(m==0) return 1;
    return comb(n%p, m%p, p)*lucas(n/p, m/p, p)%p;
}

LL crt()
{
    LL ans=0;
    for(int i=1; i<=4; i++)
    {
        LL m=(mod-1)/prime[i];
        ans=(ans+num[i]*m%(mod-1)*ksm(m, prime[i]-2, prime[i]))%(mod-1);
    }
    return ans;
}

int main()
{
    scanf("%lld%lld", &n, &g);
    if(g==mod) {printf("0\n"); return 0;}
    for(int i=1; i<=4; i++)
    {
        fac[0]=fac[1]=inv[0]=inv[1]=1;
        for(int j=2; j<=prime[i]; j++)
        {
            fac[j]=fac[j-1]*j%prime[i];
            inv[j]=inv[prime[i]%j]*(prime[i]-prime[i]/j)%prime[i];
        }
        for(int j=2; j<=prime[i]; j++) inv[j]=inv[j-1]*inv[j]%prime[i];

        for(int j=1; j*j<=n; j++)
        {
            if(n%j) continue;
            num[i]=(num[i]+lucas(n, j, prime[i]))%prime[i];
            if(j*j==n) continue;
            num[i]=(num[i]+lucas(n, n/j, prime[i]))%prime[i];
        }
    }
    printf("%lld\n", ksm(g, crt(), mod));
}

发表评论

邮箱地址不会被公开。 必填项已用*标注