1951: [Sdoi2010]古代猪文分享之数论大合集 - 综合编程类其他综合

1951: [Sdoi2010]古代猪文分享之数论大合集

2016-03-21 09:20:22 来源：ws_yzy的博客

做这个题大概需要直到以下姿势：快速幂，费马小定理，卢卡斯定理，中国剩余定理。（大概也就这些

题目大概是让求g∑d|nCdnmodp

然后根据费马小定理原式=g∑d|nCdnmod(p?1)modp

然后也就是要求指数上的这个东西 ∑d|nCdnmod(p?1)
然后p?1还不是质数。。需要分解成质因子然后用中国剩余定理合并，然后还要求组合数还要卢卡斯定理，最后特判一下g=p的情况

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define mod 999911659 //2 3 4679 35617
#define N 100001
using namespace std;
int sc()
{
    int i=0,f=1; char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar();
    return i*f;
}
ll ans[4],fac[4][35666],inv[4][35666],p[4]={2,3,4679,35617};
ll n,g,a;
void pre()
{
    for(int i=0;i<4;i++)
    {
        fac[i][0]=inv[i][0]=fac[i][1]=inv[i][1]=1;
        for(int j=2;j>=1)
        if(y&1)ans=ans*x%mod;
    return ans;
}
int main()
{
    pre();n=sc(),g=sc();a=sqrt(n);
    if(g==mod){puts("0");return 0;}
    for(int i=1;i<=a;i++)
        if(n%i==0)
        {
            solve(i);
            if(i*i!=n)solve(n/i);
        }
    for(int i=0;i<3;i++)
    {
        ll p1=p[i],p2=p[i+1],k1,k2;
        p[i+1]=p[i+1]*p[i];
        ex_gcd(p1,p2,k1,k2);
        k1=k1%p2*(ans[i+1]-ans[i]);
        ans[i+1]=(k1*p1+ans[i])%p[i+1];
    }
    printf("%d\n",cal(g,(ans[3]+p[3])%p[3]));
    return 0;
}

点击复制链接与好友分享!回本站首页