题意
传送门 HDU 4335 What is N?
题解
根据拓展欧拉定理，当指数部分
e
≥
p
h
i
(
P
)
e\geq phi(P)
e≥phi(P)，则可以处理为
e
m
o
d
??
p
h
i
(
P
)
+
p
h
i
(
P
)
e\mod phi(P)+phi(P)
emodphi(P)+phi(P)。对于底数部分，模
P
P
P 意义下只有
[
0
,
P
)
[0,P)
[0,P) 共
P
P
P 种可能；考虑模
P
P
P 意义下数为
x
x
x 的情况，对于
y
=
x
+
k
×
P
,
k
≥
1
y=x+k\times P,k\geq 1
y=x+k×P,k≥1，有
x
+
k
×
P
≥
P
>
p
h
i
(
P
)
x+k\times P\geq P>phi(P)
x+k×P≥P>phi(P)，则
p
h
i
(
P
)
∣
(
x
+
k
×
x
)
phi(P)\mid (x+k\times x)
phi(P)∣(x+k×x)，那么只用讨论
k
=
0
k=0
k=0 与
k
>
0
k>0
k>0 两种情况。总时间复杂度
O
(
T
P
log
?
P
)
O(TP\log P)
O(TPlogP)。
运用拓展欧拉定理时，可以对指数部分的取模运算特殊处理以满足条件。 即对于
x
≥
P
x\geq P
x≥P，取模为
x
m
o
d
??
P
+
P
x\mod P+P
xmodP+P。
需要特判
M
M
M 取
U
L
L
O
N
G
_
M
A
X
ULLONG\_MAX
ULLONG_MAX 且能取到
[
0
,
M
]
[0,M]
[0,M] 的情况，此时
unsigned?long?long
\text{unsigned\ long\ long}
unsigned?long?long 会溢出。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l, _ = r; i < _; ++i)
typedef unsigned long long ll;
const int MAXP = 1e5 + 5;
int T;
ll B, P, M;
ll fac[MAXP];
ll phi(ll n)
{
ll res = n;
for (ll i = 2; i * i <= n; ++i)
{
if (n % i == 0)
{
res = res / i * (i - 1);
while (n % i == 0)
n /= i;
}
}
if (n != 1)
res = res / n * (n - 1);
return res;
}
ll mul(ll x, ll y, ll m)
{
x *= y;
return x >= m ? x % m + m : x;
}
ll pow_mod(ll x, ll n, ll m)
{
ll res = 1;
while (n)
{
if (n & 1)
res = res * x % m;
x = x * x % m, n >>= 1;
}
return res;
}
void out(int t, ll res) { cout << "Case #" << t + 1 << ": " << res << '\n'; }
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> T;
rep(t, 0, T)
{
cin >> B >> P >> M;
if (P == 1)
{
if (M == ULLONG_MAX)
{
cout << "Case #" << t + 1 << ": "
<< "18446744073709551616" << '\n';
}
else
out(t, M + 1);
continue;
}
ll p = phi(P);
fac[0] = 1;
rep(i, 1, P) fac[i] = mul(i, fac[i - 1], p);
ll res = 0;
rep(i, 0, P)
{
ll x = i;
if (x > M)
break;
res += pow_mod(x, fac[x], P) == B;
if (pow_mod(x, p, P) == B)
res += (M - x) / P;
}
out(t, res);
}
return 0;
}
|