LP2480 [SDOI2010]古代猪文 [factor]

Author Avatar
空気浮遊 2018年10月24日
  • 在其它设备中阅读本文章
  • 中国剩余定理
  • Lucas
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

Problem

https://www.luogu.org/problemnew/show/P2480

Solution

用 ubuntu 的 factor 命令分解 MOD- 1 得四个质数

然后就可以上 CRT+Lucas 了(雾)

这里主要提醒一点错误:Lucas 是>=不是>!!

Code

// Code by ajcxsu
// Problem: factor

#include<bits/stdc++.h>
#define MOD (999911659ll)
using namespace std;
typedef long long ll;

ll mo [] = {0, 2, 3, 4679, 35617};

ll inv[5][40000];
ll fac[5][40000];

ll lucas(ll n, ll m, int x) {
    if(n<m) return 0;
    if(n>=mo[x] || m>=mo[x]) return 1ll*lucas(n/mo[x], m/mo[x], x)*lucas(n%mo[x], m%mo[x], x)%mo[x];
    return 1ll*fac[x][n]*inv[x][m]*inv[x][n-m]%mo[x];
}

ll qpow(ll x, ll y, ll mo) {
    ll ret=1; x%=mo;
    while(y) {
        if(y&1ll) ret=ret*x%mo;
        x=x*x%mo, y>>=1ll;
    }
    return ret;
}

ll a[5], t[5], M[5];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int u;
    for(int i=1;i<=4;i++) {
        u=mo[i];
        inv[i][0]=inv[i][1]=fac[i][0]=fac[i][1]=1;
        for(int j=2;j<u;j++) inv[i][j]=(-1ll*(u/j)*inv[i][u%j]%u+u)%u;
        for(int j=2;j<u;j++) fac[i][j]=1ll*fac[i][j-1]*j%u, inv[i][j]=1ll*inv[i][j]*inv[i][j-1]%u;
    }

    ll g, n, ans=0;
    cin>>n>>g;
    if(!(g%MOD)) cout<<0<<endl, exit(0);
    for(int i=1;i<=4;i++) {
        for(ll j=1;j*j<=n;j++) 
            if(n%j==0) {
                if(j*j!=n) a[i]=(a[i]+lucas(n, j, i)+lucas(n, n/j, i))%mo[i];
                else a[i]=(a[i]+lucas(n, j, i))%mo[i];
            }
        M[i]=(MOD-1)/mo[i];
        t[i]=qpow(M[i], mo[i]-2, mo[i]);
        (ans+=M[i]*t[i]%(MOD-1)*a[i])%=MOD-1;
    }
    cout<<qpow(g, ans, MOD)<<endl;
    return 0;
}

本文链接:https://pst.iorinn.moe/archives/sol-luogu-2480.html
许可: https://pst.iorinn.moe/license.html
若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material