M_sea

洛谷2480 [SDOI2010]古代猪文
Luogu算法首先由题意写出答案:$\Large G^{\Sigma_{d|n}C_{n}^{\frac{d}{n...
扫描右侧二维码阅读全文
11
2018/08

洛谷2480 [SDOI2010]古代猪文

Luogu

算法

img

首先由题意写出答案:

$\Large G^{\Sigma_{d|n}C_{n}^{\frac{d}{n}}}\ mod\ 999911659$

由于每一个$\frac{d}{n}$都有对应的$d$对应,所以可以写作:

$\Large G^{\sum\limits_{d|n}C_{n}^{d}}\ mod\ 999911659$

由欧拉定理的推论可得:

$\Large {G^{\sum\limits_{d|n}C_{n}^{d}}}\equiv {G^{\sum\limits_{d|n}C_{n}^{d}\ mod\ 999911658}}\pmod{999911659}$

问题转为计算$\sum\limits_{d|n}C_{n}^{d}\ mod\ 999911658$。

分解质因数得到:$999911658=2\times 3\times 4679 \times 35617$。

枚举$n$的约数,以每个质因数为模数跑一下Lucas,然后用CRT合并。

最后跑一遍快速幂即可。

注意模数的问题。

要特判一下$g=999911659$的情况。此时直接输出$0$即可。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

const int MOD=999911659;
int fact[40000];
int a[5],m[5]={0,2,3,4679,35617};

inline int FastPow(int a,int k,int p) {
    int ans=1;
    while (k) {
        if (k&1) ans=ans*a%p;
        a=a*a%p;
        k>>=1;
    }
    return ans;
}

inline int C(int n,int m,int p) {
    if (n<m) return 0;
    return fact[n]*FastPow(fact[m],p-2,p)%p*FastPow(fact[n-m],p-2,p)%p;
}

inline int Lucas(int n,int m,int p) {
    if (m==0) return 1;
    return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}

inline int CRT(int n,int p) {
    int M=p,x=0;
    for (re int i=1;i<=n;i++) {
        int k=M/m[i]%p,t=FastPow(k,m[i]-2,m[i]);
        x=(x+a[i]*k%p*t)%p;
    }
    return x;
}

mainint main() {
    int n,g; cin>>n>>g;
    if (g==MOD) { printf("0\n"); return 0; }
    for (re int i=1;i<=4;i++) {
        fact[0]=1;
        for (re int j=1;j<=m[i];j++) fact[j]=fact[j-1]*j%m[i];
        for (re int d=1;d*d<=n;d++) {
            if (n%d) continue;
            a[i]=(a[i]+Lucas(n,d,m[i]))%m[i];
            if (n/d!=d) a[i]=(a[i]+Lucas(n,n/d,m[i]))%m[i];
        }
    }
    int p=CRT(4,MOD-1);
    cout<<FastPow(g,p,MOD)<<endl;
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 47 PM

2 条评论

  1. smy

    ???

    1. M_sea
      @smy

      orz smy

发表评论