K - Happy Equation

基本信息

题目出处	2019 山东省大学生程序设计竞赛
队伍通过率	21/307 (6.8%)

题解

通过打表可以发现，当 $a$ 为奇数时，答案为 $1$ 。

证明

当 $a$ 为奇数时，可以证明 $x = a mod 2^{p}$ 是一个解。

首先，当 $a < 2^{p}$ 时， $x = a mod 2^{p} = a$ 显然满足 $a^{x} = x^{a} (\mod 2^{p})$

当 $a \geq 2^{p}$ 时，根据模的乘法有 $a^{x} = x^{x} (\mod 2^{p})$ ，根据欧拉定理有

x^{ϕ (2^{p})} = x^{2^{p - 1}} = 1 (\mod 2^{p})

则

\begin{aligned} x^{a} & = x^{k \times 2^{p} + x} \\ = x^{2 k \times 2^{p - 1} + x} \\ = (x^{2^{p - 1}})^{2 k} \times x^{x} \\ = x^{x} \\ = a^{x} (\mod 2^{p}) \end{aligned}

$◼$

当 $a$ 为奇数时，若 $x$ 为偶数，则 $a^{x}$ 是奇数， $x^{a}$ 是偶数，不可能对 $2^{p}$ 取模后相等。因此 $x$ 也是奇数。

首先通过反证法证明以下引理。

引理 1：不存在两个奇数 $x$ 和 $y$ 满足 $x, y \in [1, 2^{p}]$ 且 $x^{a} = y^{a} (\mod 2^{p})$ 。

假设存在两个满足要求的奇数 $x$ 和 $y$ ，进行因式分解得

x^{a} - y^{a} = (x - y) \times \sum_{i = 0}^{a - 1} x^{i} y^{a - 1 - i}

$\sum$ 里的每一项都是奇数，共有 $a$ 项，奇数个奇数项加起来仍然是奇数，不存在质因子 $2$ 。而 $x - y \leq 2^{p} - 1 < 2^{p}$ ，因此质因子 $2$ 少于 $p$ 个。即

x^{a} - y^{a} \neq 0 (\mod 2^{p})

与假设矛盾。

$◼$

令 $v_{2} (t)$ 表示 $t$ 的质因数分解中 $2$ 的数量。接下来通过反证法证明以下引理。

引理 2：设 $x = y (\mod 2^{p})$ 且 $v_{2} (x) < p$ 且 $v_{2} (y) < p$ ，则 $v_{2} (x) = v_{2} (y)$ 。

不失一般性地，假设 $v_{2} (x) < v_{2} (y)$ ，由题设有

x - k_{x} \times 2^{p} = y - k_{y} \times 2^{p}

等式两边同时除以 $2^{v_{2} (x)}$ 得

\frac{x}{2^{v_{2} (x)}} - k_{x} \times 2^{p - v_{2} (x)} = \frac{y}{2^{v_{2} (y)}} - k_{y} \times 2^{p - v_{2} (x)}

$\frac{x}{2^{v_{2} (x)}}$ 是奇数，由于 $v_{2} (x) < p$ 则 $k_{x} \times 2^{p - v_{2} (x)}$ 是偶数，因此等式左边是奇数；由于 $v_{2} (x) < v_{2} (y)$ 则 $\frac{y}{2^{v_{2} (y)}}$ 是偶数，由于 $v_{2} (x) < p$ 则 $k_{y} \times 2^{p - v_{2} (x)}$ 是偶数，因此等式右边是偶数。产生矛盾。

$◼$

接下来通过反证法证明：不存在两个奇数 $x$ 和 $y$ 满足 $1 \leq x < y \leq 2^{p}$ 且 $a^{x} = x^{a} (\mod 2^{p})$ 且 $a^{y} = y^{a} (\mod 2^{p})$ 。

假设存在两个满足要求的奇数 $x$ 和 $y$ ，相减得

a^{y} - a^{x} = y^{a} - x^{a} (\mod 2^{p})

令 $v_{2} (t)$ 表示 $t$ 的质因数分解中 $2$ 的数量。由引理 1 得 $v_{2} (y^{a} - x^{a}) < p$ ，则 $v_{2} (a^{y} - a^{x}) < p$ （否则 $a^{y} - a^{x} = 0 \neq y^{a} - x^{a} (\mod 2^{p})$ ），由引理 2 得 $v_{2} (a^{y} - a^{x}) = v_{2} (y^{a} - x^{a})$

根据升幂（LTE）定理有

\begin{aligned} v_{2} (a^{y} - a^{x}) & = v_{2} (a^{x} (a^{y - x} - 1)) & （因式分解） \\ = v_{2} (a^{x} (a^{y - x} - 1^{y - x})) \\ = v_{2} (a^{x}) + v_{2} (a^{y - x} - 1^{y - x}) & （根据 v_{2} 的定义） \\ = v_{2} (a^{x}) + v_{2} (a - 1) + v_{2} (a + 1) + v_{2} (y - x) - 1 & （升幂定理） \end{aligned}

\begin{aligned} v_{2} (y^{a} - x^{a}) & = v_{2} (y - x) & （升幂定理） \end{aligned}

即

v_{2} (a^{x}) + v_{2} (a - 1) + v_{2} (a + 1) - 1 = 0

因为 $a^{x}$ 是奇数，所以 $v_{2} (a^{x}) = 0$ 。因为 $a$ 是奇数，当 $a \geq 3$ 时， $(a - 1)$ 和 $(a + 1)$ 均为正偶数，因此 $v_{2} (a - 1) \geq 1$ ， $v_{2} (a + 1) \geq 1$ 。因此

v_{2} (a^{x}) + v_{2} (a - 1) + v_{2} (a + 1) - 1 \geq 1 \neq 0

产生矛盾。

当 $a = 1$ 时，满足 $1^{x} = x^{1} (\mod 2^{p})$ 且 $x \in [1, 2^{p}]$ 的 $x$ 显然只有 $x = 1$ 。

$◼$

当 $a$ 为偶数时，设 $a$ 的质因数分解中有 $q$ 个 $2$ ，那么 $a^{x}$ 的质因数分解中就有 $q x$ 个 $2$ 。当 $q x \geq p$ 时， $a^{x} mod 2^{p} = 0$ 。因为 $a$ 是正偶数，即 $q \geq 1$ ，所以当 $x \geq p$ 时我们只要考虑满足 $x^{a} mod 2^{p} = 0$ 的 $x$ 。

同样，设 $x$ 的质因数分解中有 $k$ 个 $2$ ，那么 $x^{a}$ 的质因数分解中就有 $k a$ 个 $2$ 。为了让 $x^{a} mod 2^{p} = 0$ ，必须要有 $k a \geq p$ ，即 $k \geq ⌈ \frac{p}{a} ⌉ = k^{'}$ 。 $[p, 2^{p}]$ 中， $2^{k^{'}}$ 的倍数有 $(2^{p - k^{'}} - ⌊ \frac{p - 1}{2^{k^{'}}} ⌋)$ 个。

由于 $p \leq 30$ ， $x < p$ 的部分枚举即可。复杂度 $O (p \log (a + p))$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;

long long power(long long a, int b, int MOD) {
    long long y = 1;
    for (; b; b >>= 1) {
        if (b & 1) y = y * a % MOD;
        a = a * a % MOD;
    }
    return y;
}

void solve() {
    int a, p; scanf("%d%d", &a, &p);
    if (a & 1) { printf("1\n"); return; }

    int ans = 0;
    for (int x = 1; x < p; x++) ans += (power(a, x, 1 << p) == power(x, a, 1 << p) ? 1 : 0);
    int k = (p + a - 1) / a;
    ans += (1 << (p - k)) - (p - 1) / (1 << k);
    printf("%d\n", ans);
}

int main() {
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}