题目大意
给出一个数$x$，求出满足条件：
的$n(1\le n\le x)$的个数。
题目分析
由费马小定理：
故$a^n$存在循环节为$p-1$的循环，而$n$存在循环节为$p$的循环。
因此$n\cdot a^n$存在循环，其中一个循环节为$p\cdot(p-1)$。
令$n=i\cdot(p-1)+j$，那么可以列出下列表格（中间部分表示$n\cdot a^n$）：
| $n\cdot a^n$ |
$j=1$ |
$j=2$ |
$\cdots$ |
$j=p-1$ |
| $i=0$ |
$1\cdot a^1$ |
$2\cdot a^2$ |
$\cdots$ |
$(p-1)\cdot a^{p-1}$ |
| $i=1$ |
$0\cdot a^1$ |
$1\cdot a^2$ |
$\cdots$ |
$(p-2)\cdot a^{p-1}$ |
| $i=2$ |
$(p-1)\cdot a^1$ |
$0\cdot a^2$ |
$\cdots$ |
$(p-3)\cdot a^{p-1}$ |
| $\cdots$ |
$\cdots$ |
$\cdots$ |
$\cdots$ |
$\cdots$ |
| $i=p-1$ |
$2\cdot a^1$ |
$3\cdot a^2$ |
$\cdots$ |
$0\cdot a^{p-1}$ |
在表格中，不难发现每一项$n$的系数刚好是$j-i$。
不妨令$y=b\cdot a^{-j}$，故有同余式$j-i\equiv y\pmod p$。
因此，对于一个特定的$j$，$i$只可能为$(j-y),p+(j-y),\cdots,kp+(j-y)$。
我们可以在$x$的范围内计算$i$的合法数量。
因此问题解决。
若不考虑求逆元的时间，时间复杂度为$O(p)$。
像这类同余问题总是转化为倍数问题（Dp）或者在循环节内解决的问题（计数）。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
LL a,b,p,x,ans=0;
LL Quick_Pow(LL a,LL b) {
LL ans=1;
for(; b; b>>=1,a=a*a%p)if(b&1)ans=ans*a%p;
return ans;
}
int main() {
a=Get_Int();
b=Get_Int();
p=Get_Int();
x=Get_Int();
LL tmp=Quick_Pow(a,p-2),inv=1;
for(int j=1; j<p; j++) {
inv=inv*tmp%p;
LL y=b*inv%p;
LL first=(p-1)*((j-y+p)%p)+j;
if(first>x)continue;
ans+=(x-first)/(p*(p-1))+1;
}
printf("%I64d\n",ans);
return 0;
}
|
