AcWing 213. 古代猪文数学知识

2021-02-08 20:16

阅读：591

标签：atom close lap class sum font pre href namespace

传送门

题目描述：

给定整数n,q，计算 $q^{\sum_{d|n} C_{n}^{d}}$ mod 999911659 $q^{\sum_{d | n} C_{n}^{d}} m o d 999911659$

输入格式

输入包括一行，包含两个整数n，q，用一个空格隔开。

输出格式

输出包括一行，包含一个整数表示最终结果。

数据范围

$1 \leq n, q \leq 10^{9}$

输入样例：

4 2

输出样例：

提示:对于n的每一个正因数d，都有一个$C_{n}^{d}$ $C_{n}^{d}$

$C_{n}^{d}$

$\left\{\begin{matrix} x & mod & 2 & = & a_{1}\\ x & mod & 3 & = & a_{2} \\ x & mod & 4679 & = & a_{3} \\ x & mod & 35617 & = & a_{4} \end{matrix}\right.$

$C_{n}^{d}$

#include#define ll long long
using namespace std;
const int N = 4e4 + 10;
const ll mod = 999911659;
ll fac[N] = {1},n,q,b[5];
int a[5] = {0,2,3,4679,35617};
ll qp(ll a,ll b) {
    ll ans = 1;
    for (;b;b>>=1,a=a*a%mod) 
        if (b&1) ans = ans * a %mod;
    return ans;
}
void exgcd(ll a,ll b,ll &x,ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return ;
    }
    exgcd(b,a%b,y,x);
    y -= (a/b)*x;
}
ll getinv(ll a,ll b) {
    ll x,y;
    exgcd(a,b,x,y);
    return (x%b+b)%b;
}
ll lucas(ll x,ll p) {
    ll ans = 1;
    for (ll y = n;x;x/=p,y/=p) {
        ll a = x%p, b = y%p;
        ans = ans*fac[b]%p*getinv(fac[a],p)%p*getinv(b0:fac[b-a],p)%p;
    }
    return ans;
}
int main(){
    scanf("%lld%lld",&n,&q);
    q%=mod;
    if(!q) {
        printf("0\n");
        return 0;
    }
    ll mod1 = mod -1,ans = 0,x,y;
    for (ll i = 1; i 35617; i++) fac[i] = fac[i-1]*i%mod1;
    for (ll i = 1; i*i)
        if (n%i==0) {
            for (int j = 1; j 4; j++)
                b[j] = (b[j]+lucas(i,a[j]))%a[j];
            if (i*i!=n) for (int j = 1; j 4; j++)
                b[j] = (b[j]+lucas(n/i,a[j]))%a[j];
        }
    for (int i = 1; i 4; i++){
        exgcd(mod1/a[i],a[i],x,y);
        ans = (ans+x*(mod1/a[i])%mod*b[i])%mod1;
    }
    ans = (ans+mod1)%mod1;
    ans = qp(q,ans);
    printf("%lld\n", ans);
    return 0;
}

View Code

AcWing 213. 古代猪文数学知识

标签：atom close lap class sum font pre href namespace

原文地址：https://www.cnblogs.com/l999q/p/11335420.html

上一篇：查看API工具 https://editor.swagger.io/

下一篇：Ubuntu---gedit 打开windows 下 .txt 文件乱码的解决方法

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 213. 古代猪文数学知识
文章链接：http://soscw.com/index.php/essay/52792.html

亲，登录后才可以留言！

AcWing 213. 古代猪文数学知识

题目描述：

输入格式

输出格式

数据范围

输入样例：

输出样例：

评论

热门文章

推荐文章

最新文章

置顶文章

AcWing 213. 古代猪文 数学知识

题目描述：

输入格式

输出格式

数据范围

输入样例：

输出样例：

评论

热门文章

推荐文章

最新文章

置顶文章

AcWing 213. 古代猪文数学知识