当前位置：首页 > news >正文

【2023次方 / B】

news 来源：原创 2024/9/25 18:49:47

题目

在这里插入图片描述

思考

直接快速幂，mod值恒为2023：不可以哦，不存在这个等式 $a^{b} \equiv a^{b \; mod \; p} \; (mod \; p)$
采用小费马定理 $a^{p-1} \equiv 1 \; (mod \; p) \;,( gcd(a,p)=1)$ ，很可惜还是错的，因为2023不是质数（一个质因数为17）
- 设原式为 $b^{2022^{2023}} \; mod \; p$
- $a^{2023} \equiv 1 \cdot a \; (mod \; p)$ ，原式子被化简为 $b^{2022} \; mod \; p$
- $b^{2022} \equiv 1 \; (mod \; p)$ ，答案为1
采用欧拉定理，很可惜需要不断嵌套，而且条件不会一直满足
- $a^{\phi(p)} \equiv 1 \; (mod \; p) \;, gcd(a,p) = 1 \; \Rightarrow a^{b} \equiv a^{b\;mod\;\phi(p)} \; (mod \; p)$ 用这个
- $a^{b} \equiv a^{b} \; (mod \; p), \; b < \phi(p)$
- $a^{b} \equiv a^{b\;mod \; \phi(p) + \phi(p)} \; (mod \; p), \; b \ge \phi(p)$
采用周期法
- 首先不断计算 $a\;mod\;p,\;a^{2}\;mod\;p......a^{n}\;mod\;p$ ，直到出现循环，假设指数为 $i$ 时出现重复
- 则周期 $T = i - 1$
- 对于问题 $a^{j}\;mod\;p$ ，我们可以化简指数为 $j\;mod\;T$ 即可，注意若值为0，则改值为T，总之就是映射到 $[1, T]$ 上的某一元素

做法

计算 $2^{i} \;mod\; 2023 ,\;T = 408$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
set<LL> s;
int main()
{LL a = 2, mod = 2023;int i;LL op = a;for (i = 1;; i++){LL tmp = op % mod;if (s.count(tmp))break;elses.insert(tmp);op = (op * a) % mod; // 注意，这个求模运算不影响指数，是乘法法则的运用}int T = i - 1;cout << T;
}

计算 $3^{i} \;mod\; 408 ,\;T = 16$
计算 $4^{i} \;mod\; 16 = 0$ （其实不用计算，因为16是4的倍数，因此 $i >= 2$ 就可以得到结果为 0）
计算 $3^{16} \;mod\; 408 = 273$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL qmi(LL base, LL x, LL mod)
{LL retv = 1;while (x){if (x & 1)retv = (retv * base) % mod;base = (base * base) % mod;x >>= 1;}return retv;
}
int main()
{LL base = 3, x = 16, mod = 408;cout << qmi(base, x, mod);
}

计算 $2^{273} \;mod\; 2023 = 869$

解释

为什么有些做法不嵌套欧拉函数，只用了一层欧拉函数也可以得到这个答案？

这是因为： 2 的指数需要 $\phi(2023)$ 来化简（对应以3为底数的快速幂 mod = $\phi(2023)$ ，这个做到了），3 的指数需要 $\phi(\phi(2023))$ ，这个没做到
但是如周期法所示，3的指数，以4为底的上层对答案的影响等效于令 3 的指数为 16，而错误方法此时得到的指数是 1024， $\phi(2023) = 1632$
$\mod 1632 = 1024$ 与 16 映射到周期 $T = 16$ 的位置一致
总的来说，就是说下层一样处理，上层等效了，最狗血的是那个1024刚好是16倍数，而且没被1632影响

思考不完全对，但是答案对的示例代码

#include<bits/stdc++.h>
using namespace std;
#define int long long//欧拉函数 
int get_eular(int n){int phi=n;for(int i=2;i<=n/i;i++){if(n%i)    continue;while(n%i==0)    n/=i;phi=phi/i*(i-1);}if(n>1)    phi=phi/n*(n-1);return phi;
} //快速幂
int quick(int base, int x, int mod){int res=1;while(x){if(x&1)    res=res*base%mod;base=base*base%mod;x>>=1;}return res;
} signed main(){int a=get_eular(2023); int t=2023; for(int i=2022;i>=3;i--){t=quick(i,t,a);};t=quick(2,t,2023);cout<<t<<endl;    return 0;
}