专栏文章
题解：P12540 [XJTUPC 2025] 离散对数
P12540题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mip98lrl
- 此快照首次捕获于
- 2025/12/03 08:14 3 个月前
- 此快照最后确认于
- 2025/12/03 08:14 3 个月前
不妨令 ，则 ，因为 是质数，且 ，所以 与 互质，根据费马小定理 ，可得 。
所以
b \equiv a\pmod{p}\\
b \equiv c \pmod{p-1}
\end{cases} $$
$(p-1)(p-1) \equiv p^2-2p+1 \equiv 1\pmod{p}$，所以 $p-1$ 在模 $p$ 意义下的逆元为 $p-1$。
$p\equiv 1 \pmod{p-1}$，所以 $p$ 在模 $p-1$ 意义下的逆元为 $1$。
又因为 $p$ 与 $p-1$ 互质，根据中国剩余定理（CRT），答案即为 $(a(p-1)^2+c\cdot p) \mod{p(p-1)}$。
其中 $p(p-1)$ 接近 $10^{18}$，中间运算可能超过 `long long`，需用 `__int128`。
参考代码：
```cpp
#include<iostream>
using namespace std;
using ll=long long;
using lll=__int128;
int main(){
ll a,c,p;
cin>>a>>c>>p;
lll mod=p*(p-1);
cout<<ll((lll(a)*(p-1)%mod*(p-1)+lll(c)*p)%mod);
}
```相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...