洛谷P2480 古代猪文

时间:2022-09-20 13:36:08

这道题把我坑了好久......

原因竟是CRT忘了取正数!

题意:求洛谷P2480 古代猪文

指数太大了,首先用欧拉定理取模。

由于模数是质数所以不用加上phi(p)

然后发现phi(p)过大,不能lucas,但是它是个square free,可以分解质因数然后lucas然后CRT。

然后就没有然后了......模板套来套去......

注意CRT的结果可能是负数,要取正。

 #include <cstdio>
#include <algorithm>
#define say(a) printf(#a); printf(" = %lld \n", a) typedef long long LL;
const int N = ;
const LL MO = ;
const LL prime[] = {, , , }; int T;
LL n, G;
LL nn[][N], inv[][N], invn[][N], aa[]; inline LL qpow(LL a, LL b, LL c) {
LL ans = ;
while(b) {
if(b & ) {
ans = ans * a % c;
}
a = a * a % c;
b = b >> ;
}
return ans;
}
LL C(int a, int b) {
return nn[T][a] * invn[T][b] % prime[T] * invn[T][a - b] % prime[T];
}
LL lucas(int a, int b) {
if(!b) {
return ;
}
return C(a % prime[T], b % prime[T]) * lucas(a / prime[T], b / prime[T]) % prime[T];
}
LL exgcd(LL a, LL b, LL &x, LL &y) {
if(!b) {
x = ;
y = ;
return a;
}
LL g = exgcd(b, a % b, x, y);
std::swap(x, y);
y -= (a / b) * x;
return g;
} inline void prework(int h) {
inv[h][] = ;
LL p = prime[h];
for(int i = ; i < p; i++) {
inv[h][i] = (p - p / i) * inv[h][p % i] % p;
}
nn[h][] = ;
invn[h][] = ;
for(int i = ; i < p; i++) {
nn[h][i] = nn[h][i - ] * i % p;
invn[h][i] = invn[h][i - ] * inv[h][i] % p;
}
return;
} inline LL CRT() { LL M = MO - , ans = , b, t;
for(int i = ; i < ; i++) {
LL m = M / prime[i];
exgcd(m, prime[i], t, b);
t = (t % M + M) % M;
ans += aa[i] * m % M * t % M;
ans %= M;
} return ans;
} int main() { scanf("%lld%lld", &n, &G);
if(G == MO) {
printf("");
return ;
}
for(int i = ; i < ; i++) {
prework(i);
} for(T = ; T < ; T++) {
for(int i = ; i * i <= n; i++) {
if(n % i) {
continue;
}
aa[T] += lucas(n, i);
aa[T] %= prime[T];
if(i * i < n) {
aa[T] += lucas(n, n / i);
aa[T] %= prime[T];
}
}
//printf("aa[%d] = %lld \n", T, aa[T]);
} LL ans = CRT();
//printf("ans = %lld \n", ans); ans = qpow(G, ans, MO);
printf("%lld\n", ans);
return ;
}

AC代码

洛谷P2480 古代猪文的更多相关文章

  1. 洛谷 &lbrack;P2480&rsqb; 古代猪文

    卢卡斯定理 注意特判底数和模数相等的情况 http://www.cnblogs.com/poorpool/p/8532809.html #include <iostream> #inclu ...

  2. 洛谷 P2480 &lbrack;SDOI2010&rsqb;古代猪文 解题报告

    P2480 [SDOI2010]古代猪文 题目背景 "在那山的那边海的那边有一群小肥猪.他们活泼又聪明,他们调皮又灵敏.他们*自在生活在那绿色的大草坪,他们善良勇敢相互都关心--&quot ...

  3. 洛咕 P2480 &lbrack;SDOI2010&rsqb;古代猪文

    洛咕 P2480 [SDOI2010]古代猪文 题目是要求\(G^{\sum_{d|n}C^d_n}\). 用费马小定理\(G^{\sum_{d|n}C^d_n\text{mod 999911658} ...

  4. 【题解】古代猪文 &lbrack;SDOI2010&rsqb; &lbrack;BZOJ1951&rsqb; &lbrack;P2480&rsqb;

    [题解]古代猪文 [SDOI2010] [BZOJ1951] [P2480] 在那山的那边海的那边有一群小肥猪.他们活泼又聪明,他们调皮又灵敏.他们*自在生活在那绿色的大草坪,他们善良勇敢相互都关心 ...

  5. 【题解】P2480 &lbrack;SDOI2010&rsqb;古代猪文 - 卢卡斯定理 - 中国剩余定理

    P2480 [SDOI2010]古代猪文 声明:本博客所有题解都参照了网络资料或其他博客,仅为博主想加深理解而写,如有疑问欢迎与博主讨论✧。٩(ˊᗜˋ)و✧*。 题目描述 猪王国的文明源远流长,博大精 ...

  6. P2480 &lbrack;SDOI2010&rsqb;古代猪文

    P2480 [SDOI2010]古代猪文 比较综合的一题 前置:Lucas 定理,crt 求的是: \[g^x\bmod 999911659,\text{其中}x=\sum_{d\mid n}\tbi ...

  7. 【BZOJ1951】&lbrack;SDOI2010&rsqb;古代猪文

    [BZOJ1951][SDOI2010]古代猪文 题面 bzoj 洛谷 题解 题目实际上是要求 $ G^{\sum d|n\;C_n^d}\;mod \; 999911659 $ 而这个奇怪的模数实际 ...

  8. 【BZOJ1951】古代猪文(CRT,卢卡斯定理)

    [BZOJ1951]古代猪文(CRT,卢卡斯定理) 题面 BZOJ 洛谷 题解 要求什么很显然吧... \[Ans=G^{\sum_{k|N}{C_N^k}}\] 给定的模数是一个质数,要求解的东西相 ...

  9. luogu&lowbar;2480&colon; 古代猪文

    洛谷:2480古代猪文 题意描述: 给定两个整数\(N,G\),求$G^{\sum_{k|n}C_n^k} mod 999911659 $. 数据范围: \(1\leq N\leq 10^9,1\le ...

随机推荐

  1. &period;NET程序的性能要领和优化建议

    前几天在老赵的博客上看到,Bill Chiles (Roslyn 编译器的Program Manager)写了一篇文章叫做<Essential Performance Facts and .NE ...

  2. html弹出窗并用遮罩层的实例

    <!DOCTYPE html> <html> <head lang="en"> <meta charset="UTF-8&quo ...

  3. vs2012 编译运行报 项目程序包Dsp&period;Bds&period;dll还原失败&comma;找不到版本xxxxxx的程序包问题的解决方法

    原先vs2012程序运行项目是可以了,不会出现程序包Dsp.Bds.dll还原失败,找不到版本未2.0.1.0的程序包问题, 但是项目可以正常运行,每次调试看到下面一片红感觉不舒服 原因:可能当时我看 ...

  4. C&num; 实现抓取网站页面内容

    抓取新浪网的新闻栏目,如图所示: 使用 谷歌浏览器的查看源代码: 通过分析得知,我们所要找的内容在以下两个标签之间: <!-- publish_helper name='要闻-新闻' p_id= ...

  5. 【HDOJ】1510 White Rectangles

    这个题目很好,变形的题目也很多.简单DP. /* 1510 */ #include <cstdio> #include <cstring> #include <cstdl ...

  6. cogs 1008 贪婪大陆

    /* 不要思维定视 盯着线段树维护l r 的ans不放 显然没法区间合并 换一种思路 如果打暴力的话 O(nm) 每次询问 扫一遍之前所有的修改 有交点则说明种数++ 接下来考虑如何优化 我们把每个区 ...

  7. LeetCode OJ 230&period; Kth Smallest Element in a BST

    Total Accepted: 46445 Total Submissions: 122594 Difficulty: Medium Given a binary search tree, write ...

  8. 优先队列Priority Queue和堆Heap

    对COMP20003中的Priority queue部分进行总结.图片来自于COMP20003 queue队列,顾名思义特点先进先出 priority queue优先队列,出来的顺序按照优先级prio ...

  9. Background removal with deep learning

    [原文链接] Background removal with deep learning   This post describes our work and research on the gree ...

  10. Codeforces Round &num;449 &lpar;Div&period; 2&rpar;

    Codeforces Round #449 (Div. 2) https://codeforces.com/contest/897 A #include<bits/stdc++.h> us ...