这道题把我坑了好久......
原因竟是CRT忘了取正数!
题意:求
指数太大了,首先用欧拉定理取模。
由于模数是质数所以不用加上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 古代猪文的更多相关文章
-
洛谷 [P2480] 古代猪文
卢卡斯定理 注意特判底数和模数相等的情况 http://www.cnblogs.com/poorpool/p/8532809.html #include <iostream> #inclu ...
-
洛谷 P2480 [SDOI2010]古代猪文 解题报告
P2480 [SDOI2010]古代猪文 题目背景 "在那山的那边海的那边有一群小肥猪.他们活泼又聪明,他们调皮又灵敏.他们*自在生活在那绿色的大草坪,他们善良勇敢相互都关心--" ...
-
洛咕 P2480 [SDOI2010]古代猪文
洛咕 P2480 [SDOI2010]古代猪文 题目是要求\(G^{\sum_{d|n}C^d_n}\). 用费马小定理\(G^{\sum_{d|n}C^d_n\text{mod 999911658} ...
-
【题解】古代猪文 [SDOI2010] [BZOJ1951] [P2480]
[题解]古代猪文 [SDOI2010] [BZOJ1951] [P2480] 在那山的那边海的那边有一群小肥猪.他们活泼又聪明,他们调皮又灵敏.他们*自在生活在那绿色的大草坪,他们善良勇敢相互都关心 ...
-
【题解】P2480 [SDOI2010]古代猪文 - 卢卡斯定理 - 中国剩余定理
P2480 [SDOI2010]古代猪文 声明:本博客所有题解都参照了网络资料或其他博客,仅为博主想加深理解而写,如有疑问欢迎与博主讨论✧。٩(ˊᗜˋ)و✧*。 题目描述 猪王国的文明源远流长,博大精 ...
-
P2480 [SDOI2010]古代猪文
P2480 [SDOI2010]古代猪文 比较综合的一题 前置:Lucas 定理,crt 求的是: \[g^x\bmod 999911659,\text{其中}x=\sum_{d\mid n}\tbi ...
-
【BZOJ1951】[SDOI2010]古代猪文
[BZOJ1951][SDOI2010]古代猪文 题面 bzoj 洛谷 题解 题目实际上是要求 $ G^{\sum d|n\;C_n^d}\;mod \; 999911659 $ 而这个奇怪的模数实际 ...
-
【BZOJ1951】古代猪文(CRT,卢卡斯定理)
[BZOJ1951]古代猪文(CRT,卢卡斯定理) 题面 BZOJ 洛谷 题解 要求什么很显然吧... \[Ans=G^{\sum_{k|N}{C_N^k}}\] 给定的模数是一个质数,要求解的东西相 ...
-
luogu_2480: 古代猪文
洛谷:2480古代猪文 题意描述: 给定两个整数\(N,G\),求$G^{\sum_{k|n}C_n^k} mod 999911659 $. 数据范围: \(1\leq N\leq 10^9,1\le ...
随机推荐
-
.NET程序的性能要领和优化建议
前几天在老赵的博客上看到,Bill Chiles (Roslyn 编译器的Program Manager)写了一篇文章叫做<Essential Performance Facts and .NE ...
-
html弹出窗并用遮罩层的实例
<!DOCTYPE html> <html> <head lang="en"> <meta charset="UTF-8&quo ...
-
vs2012 编译运行报 项目程序包Dsp.Bds.dll还原失败,找不到版本xxxxxx的程序包问题的解决方法
原先vs2012程序运行项目是可以了,不会出现程序包Dsp.Bds.dll还原失败,找不到版本未2.0.1.0的程序包问题, 但是项目可以正常运行,每次调试看到下面一片红感觉不舒服 原因:可能当时我看 ...
-
C# 实现抓取网站页面内容
抓取新浪网的新闻栏目,如图所示: 使用 谷歌浏览器的查看源代码: 通过分析得知,我们所要找的内容在以下两个标签之间: <!-- publish_helper name='要闻-新闻' p_id= ...
-
【HDOJ】1510 White Rectangles
这个题目很好,变形的题目也很多.简单DP. /* 1510 */ #include <cstdio> #include <cstring> #include <cstdl ...
-
cogs 1008 贪婪大陆
/* 不要思维定视 盯着线段树维护l r 的ans不放 显然没法区间合并 换一种思路 如果打暴力的话 O(nm) 每次询问 扫一遍之前所有的修改 有交点则说明种数++ 接下来考虑如何优化 我们把每个区 ...
-
LeetCode OJ 230. Kth Smallest Element in a BST
Total Accepted: 46445 Total Submissions: 122594 Difficulty: Medium Given a binary search tree, write ...
-
优先队列Priority Queue和堆Heap
对COMP20003中的Priority queue部分进行总结.图片来自于COMP20003 queue队列,顾名思义特点先进先出 priority queue优先队列,出来的顺序按照优先级prio ...
-
Background removal with deep learning
[原文链接] Background removal with deep learning This post describes our work and research on the gree ...
-
Codeforces Round #449 (Div. 2)
Codeforces Round #449 (Div. 2) https://codeforces.com/contest/897 A #include<bits/stdc++.h> us ...