题目大意
地主家的傻儿子企鹅豆豆觉得自己太笨了，决定做一些数学题来提高智商。
但是看到第一道题就傻眼了。所以他拿着题跑过来找你。
给定两个数字$a$和$n$，求有多少数字$b$满足$a^b\equiv b^a\pmod{2^n}$，且$1\le b\le 2^n$。
为了能吃上豆豆家的鳕鱼，你励志要把这道题做出来！
题目分析
打表找规律，发现当$a$是奇数时答案始终是$1$，具体证明题解中有讲。
对于$a$是偶数的情况，$b$必定也是偶数。
当$b\gt n$时，不难发现$a^b\equiv0\pmod{2^n}$，则$b^a\equiv0\pmod{2^n}$。
则$b$中至少含有$\lceil\frac na\rceil$个因子$2$，故此时的答案个数为$\frac{2^n}{2^{\lceil\frac na\rceil}}$，但重复计算了$b\le n$的情况，将其减掉：$\frac{2^n}{2^{\lceil\frac na\rceil}}-\frac{n}{2^{\lceil\frac na\rceil}}$
否则当$b\le n$的时候，暴力找就可以了。
代码
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
53
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int 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;
}
typedef long long LL;
int t,a,n;
LL Quick_Pow(LL a,LL b,LL mod) {
LL sum=1;
while(b) {
if(b&1)sum=sum*a%mod;
a=a*a%mod;
b>>=1;
}
return sum;
}
int main() {
t=Get_Int();
while(t--) {
a=Get_Int();
n=Get_Int();
int mod=1<<n;
if(a&1) {
puts("1");
continue;
}
int ans=0;
for(int i=2; i<=n; i+=2)
if(Quick_Pow(a,i,mod)==Quick_Pow(i,a,mod))ans++;
int c=ceil((double)n/a);
ans+=((1<<n)>>c)-(n>>c);
printf("%d\n",ans);
}
return 0;
}
|
