[SDOI2010]古代猪文（欧拉，卢卡斯，中国剩余）-白红宇

[SDOI2010]古代猪文（欧拉，卢卡斯，中国剩余）

阅读量：5159 次

发布时间：2019-06-13

本文共 1470 字，大约阅读时间需要 4 分钟。

\(solution:\)

这道题感觉综合性极强，用到了许多数论中的知识：

质因子，约数，组合数

欧拉定理

卢卡斯定理

中国剩余定理

首先我们读题，发现题目需要我们枚举k（就是n的所有约数），并且对于每一个k都要用一个组合数算出其情况数（读题：不过具体是哪k分之一。这句话说明我们可以从n中取出任意k个字，所以情况数就是\(C(_n^k)\) ）（然后因为我们求的组合数范围有点大，所以需要用卢卡斯定理来求组合数（接下来我们会发现模数其实比较小））。但是这道题目把所有情况数（设有tot个情况），求为\(G^{tot}\) 作答案输出。

众所周知，指数是不能直接取模的，所以我们要用到欧拉定理（注意欧拉定理建立在\(gcd(G,999911659)=1\) 的情况下，所以读入时要特判！）。

\(G^{tot}=G^{(tot\ mod \ \phi(P)+\phi(P))}\ mod(P)\)

因为我们的模数为999911659（质数），所以我们其实就是要求这个东西：

\(G^{(tot\ mod \ 999911658+999911658)}\)

但是我们发现虽然我们现在可以取模了，但是999911658并不是一个质数，而我们求tot的时候是需要用卢卡斯的，所以我们必须保证模数是一个质数且不能太大。所以我们又得用上中国剩余定理，\(999911658=2\times 3\times 4679\times 35617\)

于是我们分别求出在\(mod\ 2 \ ，mod\ 3，mod \ 4679，mod \ 35617\) 意义下的所有tot，然后就需要中国剩余定理解出我们真正的\(mod \ 999911658\) 意义下的tot是多少，然后就可以直接搞快速幂求答案了！

\(code:\)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #define ll long long#define db double#define mod 999911658#define rg register intusing namespace std;ll n,g,ans;ll a[4];ll jc[40005];ll m[4]={2,3,4679,35617};inline ll qr(){ char ch; while((ch=getchar())<'0'||ch>'9'); ll res=ch^48; while((ch=getchar())>='0'&&ch<='9') res=res*10+(ch^48); return res;}inline ll ksm(ll x,ll y,ll p){ ll res=1; x%=p; while(y){ if(y&1)res=res*x%p; x=x*x%p; y>>=1; }return res;}inline ll c(ll x,ll y,ll p){ //组合数 if(x

转载于:https://www.cnblogs.com/812-xiao-wen/p/10698494.html

你可能感兴趣的文章