目录
在 \(O(\sqrt{p})\) 的时间内求解
其中 \(a\perp p\)，方程的解 \(x\) 满足 \(0 \le x < p\)。
首先根据费马小定理 \(a^{p-1}\equiv1\pmod{p}\)，不难发现 \(1\sim p-1\) 是一个循环节，也就是说只用判断 \(1\sim p-1\) 这些数里是否存在一个方程的解 \(x\) 即可。
但是这个范围仍然很大，直接 \(O(p)\) 跑肯定不行。
令 \(x=A\left\lceil\sqrt{p}\right\rceil-B (0\le A, B\le\left\lceil\sqrt{p}\right\rceil)\)，则 \(a^{A\left\lceil\sqrt{p}\right\rceil-B} \equiv b \pmod p\)。
则 \(a^{A\left\lceil\sqrt{p}\right\rceil} \equiv a^{B} b \pmod p\)。
由于 \(A,B\) 不大，我们可以枚举出所有 \(a^{B} b\) 和 \(a^{A\left\lceil\sqrt{p}\right\rceil}\) 的取值。用 map 存下所有 \(a^{B} b\) 的取值，再查找 \(a^{A\left\lceil\sqrt{p}\right\rceil}\) 的取值是否出现过即可。
注意在求出满足 \(a^{A\left\lceil\sqrt{p}\right\rceil} \equiv a^{B} b \pmod p\) 的合法 \(A,B\) 后还要推回到 \(a^{A\left\lceil\sqrt{p}\right\rceil-B} \equiv b \pmod p\) 才能得到解 \(x=A\left\lceil\sqrt{p}\right\rceil-B (0\le A, B\le\left\lceil\sqrt{p}\right\rceil)\)，这一步要求 \(a\perp p\)，但不要求 \(p\in\mathbb{P}\)。
时间复杂度：\(O(\sqrt{p}\log_2\sqrt{p})\)。
你想更快的话你用哈希表也行。
板子题，放一份代码。
inline ll FastPow (ll a, ll b, ll P) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % P;
a = a * a % P, b >>= 1;
}
return ans;
}
inline void Solve () {
ll qp = ceil (sqrt (p));
_for (i, 0, qp) h[n * FastPow (b, i, p) % p] = i;
ll t = FastPow (b, qp, p), num = 1;
_for (i, 1, qp) {
num = num * t % p;
if (h[num]) {
ans = (i * qp % p - h[num] + p) % p;
return;
}
}
return;
}
推式子题。
那么：
令 \(i - 1 = A \left \lceil \sqrt p \right \rceil - B\)，则 \(a^{A \left \lceil \sqrt p \right \rceil - B} \equiv \dfrac{t + \frac{b}{a-1}}{x_{1}+\frac{b}{a-1}} \pmod{p}\)。
则：
就可以跑 BSGS 了。
但是还有几个细节：
是不是再来一个 CRT 就同余全家桶了。
裸的逆元和 BSGS，但是题目只保证 \(p\in\mathbb{P}\) 不保证 \(y\perp p\)，需要特判一下 \(p\) 是否为 \(y\) 的倍数。
if (!y) { ans = (z % p ? -1 : 1); return; }
定义一个矩阵的类然后直接跑就行，感觉没啥大区别。
const ll N = 110;
namespace SOLVE {
ll n, p, ans;
class Matrix {
public:
ll len, m, ma[N][N];
inline void Init (ll l, ll md) {
len = l, m = md;
memset (ma, 0, sizeof (ma));
_for (i, 1, l) ma[i][i] = 1;
return;
}
inline void Print () {
_for (i, 1, n) {
_for (j, 1, n) {
printf ("%lld ", ma[i][j]);
}
puts ("");
}
puts ("");
return;
}
ll* operator [] (ll x) { return ma[x]; }
Matrix operator * (Matrix another) const {
Matrix ans;
ans.Init (len, m);
memset (ans.ma, 0, sizeof (ans.ma));
_for (i, 1, len) _for (j, 1, len) _for (k, 1, len)
ans[i][j] = (ans[i][j] + ma[i][k] * another[k][j] % m) % m;
return ans;
}
bool operator == (Matrix another) const {
_for (i, 1, n) _for (j, 1, n) if (ma[i][j] != another[i][j]) return 0;
return 1;
}
bool operator < (Matrix another) const {
_for (i, 1, len) _for (j, 1, len) {
if (ma[i][j] < another[i][j]) return 1;
if (ma[i][j] > another[i][j]) return 0;
}
return 0;
}
} a, b;
std::map <Matrix, ll> mp;
inline ll rnt () {
ll x = 0, w = 1; char c = getchar ();
while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
return x * w;
}
inline Matrix FastPow (Matrix a, ll b, ll P) {
Matrix ans;
ans.Init (n, P);
while (b) {
if (b & 1) ans = ans * a;
a = a * a, b >>= 1;
}
return ans;
}
inline void In () {
n = rnt (), p = rnt ();
a.Init (n, p), b.Init (n, p);
_for (i, 1, n) _for (j, 1, n) a[i][j] = rnt ();
_for (i, 1, n) _for (j, 1, n) b[i][j] = rnt ();
return;
}
inline void Solve () {
ll qp = ceil (sqrt (p));
_for (i, 0, qp) mp[b] = i, b = b * a;
a = FastPow (a, qp, p);
Matrix mat; mat.Init (n, p);
_for (i, 1, qp) {
mat = mat * a;
if (mp[mat]) {
ans = (i * qp % p - mp[mat] + p) % p;
return;
}
}
return;
}
inline void Out () {
printf ("%lld\n", ans);
return;
}
}
目录前言滤波电路科普主要分类实际情况单位的概念常用评价参数函数型滤波器简单分析滤波电路构成低通滤波器RC低通滤波器RL低通滤波器高通滤波器RC高通滤波器RL高通滤波器部分摘自《LC滤波器设计与制作》，侵权删。前言最近需要学习放大电路和滤波电路，但是由于只在之前做音乐频谱分析仪的时候简单了解过一点点运放，所以也是相当从零开始学习了。滤波电路科普主要分类滤波器：主要是从不同频率的成分中提取出特定频率的信号。有源滤波器：由RC元件与运算放大器组成的滤波器。可滤除某一次或多次谐波，最普通易于采用的无源滤波器结构是将电感与电容串联，可对主要次谐波（3、5、7）构成低阻抗旁路。无源滤波器：无源滤波器，又称
最近在学习CAN，记录一下，也供大家参考交流。推荐几个我觉得很好的CAN学习，本文也是在看了他们的好文之后做的笔记首先是瑞萨的CAN入门，真的通透；秀！靠这篇我竟然2天理解了CAN协议！实战STM32F4CAN！原文链接：https://blog.csdn.net/XiaoXiaoPengBo/article/details/116206252CAN详解（小白教程）原文链接：https://blog.csdn.net/xwwwj/article/details/105372234一篇易懂的CAN通讯协议指南1一篇易懂的CAN通讯协议指南1-知乎(zhihu.com)视频推荐CAN总线个人知识总
深度学习部署：Windows安装pycocotools报错解决方法1.pycocotools库的简介2.pycocotools安装的坑3.解决办法更多Ai资讯：公主号AiCharm本系列是作者在跑一些深度学习实例时，遇到的各种各样的问题及解决办法，希望能够帮助到大家。ERROR:Commanderroredoutwithexitstatus1:'D:\Anaconda3\python.exe'-u-c'importsys,setuptools,tokenize;sys.argv[0]='"'"'C:\\Users\\46653\\AppData\\Local\\Temp\\pip-instal
我完全不是程序员，正在学习使用Ruby和Rails框架进行编程。我目前正在使用Ruby1.8.7和Rails3.0.3，但我想知道我是否应该升级到Ruby1.9，因为我真的没有任何升级的“遗留”成本。缺点是什么？我是否会遇到与普通gem的兼容性问题，或者甚至其他我不太了解甚至无法预料的问题？ 最佳答案 你应该升级。不要坚持从1.8.7开始。如果您发现不支持1.9.2的gem，请避免使用它们(因为它们很可能不被维护)。如果您对gem是否兼容1.9.2有任何疑问，您可以在以下位置查看:http://www.railsplugins.or
如何学习ruby的正则表达式？(对于假人) 最佳答案 http://www.rubular.com/在Ruby中使用正则表达式时是一个很棒的工具，因为它可以立即将结果可视化。 关于ruby-我如何学习ruby的正则表达式？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/1881231/
深度学习12.CNN经典网络VGG16一、简介1.VGG来源2.VGG分类3.不同模型的参数数量4.3x3卷积核的好处5.关于学习率调度6.批归一化二、VGG16层分析1.层划分2.参数展开过程图解3.参数传递示例4.VGG16各层参数数量三、代码分析1.VGG16模型定义2.训练3.测试一、简介1.VGG来源VGG（VisualGeometryGroup）是一个视觉几何组在2014年提出的深度卷积神经网络架构。VGG在2014年ImageNet图像分类竞赛亚军，定位竞赛冠军；VGG网络采用连续的小卷积核（3x3）和池化层构建深度神经网络，网络深度可以达到16层或19层，其中VGG16和VGG
文章目录1、自相关函数ACF2、偏自相关函数PACF3、ARIMA(p,d,q)的阶数判断4、代码实现1、引入所需依赖2、数据读取与处理3、一阶差分与绘图4、ACF5、PACF1、自相关函数ACF自相关函数反映了同一序列在不同时序的取值之间的相关性。公式：ACF(k)=ρk=Cov(yt,yt−k)Var(yt)ACF(k)=\rho_{k}=\frac{Cov(y_{t},y_{t-k})}{Var(y_{t})}ACF(k)=ρk=Var(yt)Cov(yt,yt−k)其中分子用于求协方差矩阵，分母用于计算样本方差。求出的ACF值为[-1,1]。但对于一个平稳的AR模型，求出其滞
写在之前Shader变体、Shader属性定义技巧、自定义材质面板，这三个知识点任何一个单拿出来都是一套知识体系，不能一概而论，本文章目的在于将学习和实际工作中遇见的问题进行总结，类似于网络笔记之用，方便后续回顾查看，如有以偏概全、不祥不尽之处，还望海涵。1、Shader变体先看一段代码......Properties{ [KeywordEnum(on,off)]USL_USE_COL("IsUseColorMixTex?",int)=0 [Toggle(IS_RED_ON)]_IsRed("IsRed?",int)=0}......//中间省略，后续会有完整代码 #pragmamulti_c
TCL脚本语言简介•TCL（ToolCommandLanguage）是一种解释执行的脚本语言（ScriptingLanguage）,它提供了通用的编程能力：支持变量、过程和控制结构；同时TCL还拥有一个功能强大的固有的核心命令集。TCL经常被用于快速原型开发，脚本编程，GUI和测试等方面。•实际上包含了两个部分：一个语言和一个库。首先，Tcl是一种简单的脚本语言，主要使用于发布命令给一些互交程序如文本编辑器、调试器和shell。由于TCL的解释器是用C\C++语言的过程库实现的，因此在某种意义上我们又可以把TCL看作C库，这个库中有丰富的用于扩展TCL命令的C\C++过程和函数，所以，Tcl是
按照目前的情况，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visitthehelpcenter指导。关闭9年前。我来自C、php和bash背景，很容易学习，因为它们都有相同的C结构，我可以将其与我已经知道的联系起来。然后2年前我学了Python并且学得很好，Python对我来说比Ruby更容易学。然后从去年开始，我一直在尝试学习Ruby，然后是Rails，我承认，直到现在我还是学不会，讽刺的是那些打着简单易学的烙印，但是对于我这样一个老练的程序员来说，我只是无法将它