首页 > 其他分享 >简单的数学题 题解

简单的数学题 题解

时间:2024-04-20 23:26:38浏览次数:21  
标签:pmod 题解 bmod solve varphi text 简单 数学题 equiv

题意:解方程

\[ a^x\equiv x\pmod m \]

数据范围:\(a<m\le10^9\)

Solution

首先 \(a^x\equiv a^{x\bmod\varphi(m)+\varphi(m)}\pmod m\)

我们设 \(\text{solve}(\&x,y,m)\) 表示解决

\[a^{x\bmod\varphi(m)+y}\equiv x\pmod m \]

原题即 \(\text{solve}(\&x,\varphi(m),m)\)

则 \(\text{solve}(\&x,y,m)\) 相当于

\[\begin{cases}r&\equiv x\pmod{\varphi(m)}\\a^{r+y}&\equiv x\pmod m\end{cases} \]

\[x=r+k_1\varphi(m)=a^{r+y}+k_2m \]

\[k_1\varphi(m)-k_2m=a^{r+y}-r \]

\[k\cdot\gcd(\varphi(m),m)=a^{r+y}-r \]

记 \(g=\gcd(\varphi(m),m)\)

\[a^{r+y}-r\equiv0\pmod g \]

\[a^{r+y}\equiv r\pmod g \]

\[a^{r\bmod\varphi(g)+[y\bmod\varphi(g)+\varphi(g)]}\equiv r\pmod g \]

问题变成了 \(\text{solve}(\&r,[y\bmod\varphi(g)+\varphi(g)],g)\)

如果 \(r\) 解决了,那么解出 \(k_1\varphi(m)-k_2m=a^{r+y}-r\),\(x=r+k_1\varphi(m)\)

由于 \(g\) 总是小于 \(m\),问题量总是在缩小

\(m=1\) 时返回 \(x=1\)

省流

\(\text{solve}(y,m)\):

  • \(m=1\):返回 \(1\)
  • \(m>1\):
    • 记 \(g=\gcd(\varphi(m),m)\)
    • 调用 \(\text{solve}(y\bmod\varphi(g)+\varphi(g),g)\),记结果为 \(r\)
    • 解方程 \(k_1\varphi(m)-k_2m=a^{r+y}-r\)
    • 返回 \(r+k_1\varphi(m)\)

答案:\(\text{solve}(\varphi(m),m)\)

标签:pmod,题解,bmod,solve,varphi,text,简单,数学题,equiv
From: https://www.cnblogs.com/laijinyi/p/18148385

相关文章

  • 数表 题解
    “当你想不出来一道题的时候就想一下排序”先不考虑\(a\),求\[\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^m\sigma_1(\gcd(i,j))\\=&\sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^{\min(n,m)}[d=\gcd(i,j)]\sigma_1(d)\\=&\sum_{d=1}^{\min(n,m)}\sigma_1(d)\sum_......
  • 最大幂指数 题解
    Statement\(f(x)\)表示\(x\)所含质因子的最大幂指数,对于\(T=10^4\),\(a,b\le10^7\),求\[\sum_{i=1}^a\sum_{j=1}^bf(\gcd(i,j))\]时限2sSolution\[\begin{aligned}&\sum_{i=1}^a\sum_{j=1}^bf(\gcd(i,j))\\=&\sum_{i=1}^a\sum_{j=1}^b\sum_{......
  • 一个人的数论 题解
    Solution令指数为\(k\)正常反演得到\[\sum_{d\midn}\mu(d)d^k\sum_{i=1}^{\fracnd}i^k\]设\(f(x)=\sum_{i=1}^xi^k\),它是一个关于\(x\)的\(k+1\)次多项式求这个多项式可以插值\(\mathcalO(n^2)\)(推荐)高斯消元(待定系数法)\(\mathcalO(n^3)\)直接伯努利数\(\ma......
  • 重建计划 题解
    题意:一棵树,有边权,求边权平均值最大且经过点数在\([L,R]\)的路径长度.Solution首先二分答案\(x\),每条边权减去\(x\)后问题转为求最大路径长度,若答案\(\ge0\)则可行1边分治保平安。先转二叉树,这里有两种方法:一种是像线段树一样建,另一种是普通贪心的建,反正都可以然后边......
  • 题解:P10365 [PA2024] Kraniki(评分:8.4)
    前言我们一场模拟赛的题,结果原题是新鲜出炉的。小弟不才,感觉这题是做过的题中几乎最复杂的了。既然搞懂了,就来写一发题解吧。(题外话:目前最优解,我的常数真是小小又大大啊)"Upanddown,glowin'round..."Solution1、一个经典的Trick直接模拟每一种情况显然不可取,考虑计算每......
  • 染色问题 题解
    \(f(i)\):满足\(n\)行\(m\)列每行每列都有颜色,最多用了\(j\)种颜色的方案数根据容斥原理\[f(i)=[(i+1)^m-1]^n-\sum_{i=1}^m(-1)^{k-1}C_m^k[(i+1)^{m-k}-1]^n\]意思是对于每一行,每个格子都可以填\(i\)种颜色或不填;但是整行不能一个格子都不填色,所以减一;而有\(n\)行,......
  • 俄罗斯方块 题解
    题意:矩阵checkmax、矩阵求max,checkmax的值一定比当前矩阵原max大外层线段树每个节点开一棵线段树,每个点记录列的max与checkmax的标记checkmax时:对路过的点的max更新,对完全包含的区间的checkmax标记更新求max时:对路上的checkmax与完全包含的max更新\((a,b......
  • P3281 数数 题解
    j带来的贡献:\(f[i]*b^{j-i}+\sum(i\cdot\text{num}[i+1..j])+pre_{j-i}\)\(\displaystyle\sum_{j=i+1}^n\left\{f[i]*b^{j-i}+i\cdot\dfrac{b^{j-i}(b^{j-i}-1)}2+pre_{j-i}\right\}\)\(\displaystyle\sum_{j=1}^{n-i}\left\{f[i]*b^j+i\cdot\dfrac{b^j(......
  • 解析几何简单计算
    设点设线例题1题目已知椭圆方程\(\dfrac{x^2}{4}+y^2=1\),设直线\(l\),不经过点\(P(0,1)\)且与椭圆相交于\(A,B\)两点,若直线\(PA\)与直线\(PB\)的斜率和为\(-1\),证明:直线\(l\)过定点。题解由直线\(l\)不过点\(P(0,1)\)可设直线\(l\)方程:\(mx+n(y-1)=1\)......
  • 数学题 3
    T1Statement对于\(n,m,T\le50000\),求\(\sum_{i\in[1..n]}\sum_{j\in[1..m]}d(ij)\)Solution因为\(d(ij)=\sum_{u|i}\sum_{v|j}[\gcd(u,v)=1]\)\[\begin{aligned}&\sum_{i\in[1..n]}\sum_{j\in[1..m]}d(ij)\\=&\sum_{i\in[1..n]}\......