Codeforces 919E Congruence Equation(循环节+数论)
2024-10-21 03:17:39
题意
给$n, m, p, x$,求有多少个$n(1\leq n \leq x)$使得$n·a^{n}=b(\textrm{mod}\;p)$成立
思路
考虑一下左边的循环节长度,由于$n%p$的循环节长度为$p$,$a^{n}%p$的循环节长度为$p-1$(根据费马小定理$a^{0}=a^{p-1}=1(\textrm{mod}\;p)$),所以(大胆猜测)左边的循环节长度就是$p*(p-1)$。接下来,设$n=k*(p-1)+i$,有原式:
$n·a^{n}=b(\textrm{mod}\;p)$
$n=b*a^{-n}(\textrm{mod}\;p)$
$k*(p-1)+i=b*a^{-k*(p-1)-i}(\textrm{mod}\;p)$
$-k+i=b*a^{-i}(\textrm{mod}\;p)$
$k=i-b*a^{-i}(\textrm{mod}\;p)$
由于$a^{i}(\textrm{mod}\;p)$的值至多$p-1$个,所以枚举$i$即可算出$k$,即可算出$n=k*(p-1)+i$此为当前$i$下$n$的最小值,然后算一下加了循环节长度之后有多少满足的$n$即可。
Code
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl using namespace std;
typedef long long ll; const int N = 1e6 + 5; ll a, b, p, x, ans, pw[N]; ll fpow(ll a, ll b, ll mod) {
ll res = 1; a %= mod;
for(; b; b >>= 1, a = a * a % mod) if(b & 1) res = res * a % mod;
return res;
} int main() {
scanf("%lld%lld%lld%lld", &a, &b, &p, &x);
ll G = p * (p - 1);
for(int i = 1; i <= p - 1; i++) {
pw[i] = i == 1 ? a : pw[i - 1] * a % p;
ll k = ((i - b * fpow(pw[i], p - 2, p) % p) % p + p) % p;
if(x >= k * (p - 1) + i) ans += (x - k * (p - 1) - i) / G + 1;
}
printf("%lld\n", ans);
}
最新文章
- 输入URL到展现页面的全过程
- SpreadJS电子表格
- Java Struts2 POI创建Excel文件并实现文件下载
- ThinkPHP 3.2.3 Widget 扩展的使用
- WinAPI: ExtCreateRegion - 区域变换
- 集成Spring事物管理
- 如何在 Arch Linux 中安装 DNSCrypt 和 Unbound
- HTTP详解(1)-工作原理
- C语言标准
- SQL语句 递归
- 【风马一族_Android】Android 前端内容1
- 亲测 安装windows7
- Oracle单表的复杂查询
- javascript面向对象个人理解
- kali下安装截图软件
- docker容器实战-----初级<;2>;
- excle中表引用
- Mac定时关机、重启、休眠命令行
- vue离开页面销毁定时器
- 选择监听事件ItemListener(是否被选择)