频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
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;
}

 

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 合集 数论
上一篇:Web后端语言模拟http请求(带用户名和密码)实例代码大全分享
下一篇:hibernate与mybatis的比较分析
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站