题目
传送门 to HDU
思路
乱推式子，然后瞎猜。首先推成
x
(
x
−
1
)
≡
0
(
m
o
d
n
)
x(x-1)\equiv 0\pmod n
x(x−1)≡0(modn)
然后发现
x
x
x 和
x
−
1
x-1
x−1 互质，所以不难想到，
n
n
n 的所有质因数是恰属于其中一个的。
——举例，若
2
3
∣
n
2^3|n
23∣n ，则
2
3
∣
x
2^3|x
23∣x 且
x
−
1
x-1
x−1 为奇数或者
2
3
∣
(
x
−
1
)
2^3|(x-1)
23∣(x−1) 且
x
x
x 为奇数。
如何枚举？显然二者互补，且互质。于是就是满足如下条件的
⟨
p
,
q
⟩
\langle p,q\rangle
⟨p,q⟩ 的数量：
p
q
=
n
,
gcd
(
p
,
q
)
=
1
pq=n,\;\gcd(p,q)=1
pq=n,gcd(p,q)=1
然后这时候我们认为
x
=
k
1
p
,
x
−
1
=
k
2
q
x=k_1p,\;x-1=k_2q
x=k1p,x−1=k2q
如何构造？明显是式子
k
1
p
−
k
2
q
=
1
k_1p-k_2q=1
k1p−k2q=1
此时考虑
k
1
k_1
k1 的范围。因为
0
≤
x
=
k
1
p
<
n
=
p
q
0\le x=k_1p<n=pq
0≤x=k1p<n=pq ，所以
0
≤
k
1
<
q
0\le k_1<q
0≤k1<q
而
gcd
(
p
,
q
)
=
1
\gcd(p,q)=1
gcd(p,q)=1 保证存在一个解，
k
1
k_1
k1 通解是
k
1
′
+
r
q
k_1'+rq
k1′+rq ，所以长度为
q
q
q 的区间中，有且仅有 一个解。这个解足以构造出
x
x
x 。所以答案就是
⟨
p
,
q
⟩
\langle p,q\rangle
⟨p,q⟩ 的数量。
而
p
,
q
p,q
p,q 的数量是啥子呢？就是每种质因数放到左边还是右边。就是
2
c
n
t
2^{cnt}
2cnt
c
n
t
cnt
cnt 用欧拉筛，就结束了。
代码
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std
;
typedef long long int_
;
inline int readint(){
int a
= 0; char c
= getchar(), f
= 1;
for(; c
<'0'||c
>'9'; c
=getchar())
if(c
== '-') f
= -f
;
for(; '0'<=c
&&c
<='9'; c
=getchar())
a
= (a
<<3)+(a
<<1)+(c
^48);
return a
*f
;
}
const int MaxN
= 10000005;
int cnt
[MaxN
];
bool isPrime
[MaxN
];
vector
< int > primes
;
void sieve(int n
){
for(int i
=2; i
<=n
; ++i
)
isPrime
[i
] = true;
for(int i
=2,len
=0; i
<=n
; ++i
){
if(isPrime
[i
]){
++ len
, cnt
[i
] = 1;
primes
.push_back(i
);
}
for(int j
=0; j
<len
; ++j
){
if(primes
[j
] > n
/i
) break;
isPrime
[primes
[j
]*i
] = 0;
cnt
[primes
[j
]*i
] = cnt
[i
]+1;
if(i
%primes
[j
] == 0){
-- cnt
[primes
[j
]*i
];
break;
}
}
}
}
int qkpow(int_ bas
,int q
,int Mod
){
int ans
= 1;
for(; q
; q
>>=1,bas
=bas
*bas
%Mod
)
if(q
&1) ans
= ans
*bas
%Mod
;
return ans
;
}
int main(){
sieve(MaxN
-5);
for(int i
=2; i
<=MaxN
-5; ++i
)
cnt
[i
] += cnt
[i
-1];
int n
, m
; scanf("%*d");
while(~scanf("%d",&n
)){
scanf("%d",&m
);
printf("%d\n",qkpow(2,cnt
[n
],m
));
}
return 0;
}
