【HDU-6189】Law of Commutation

【HDU-6189】Law of Commutation

问题链接:https://vjudge.net/problem/HDU-6189

Solution:

没有头绪的时候先打个表,找找规律。说到打表,用python会很方便:

from math import pow
for a in range(1, 6):
    for n in range(1, 5):
        m = int(pow(2, n))
        cnt = 0
        for b in range(1, m + 1):
            if int(pow(a, b)) % m == int(pow(b, a)) % m:
                cnt = cnt + 1
                # print("a = ", a, "b = ", b, ", pow(a, b) = ", pow(a, b), ", pow(b, a) = ", int(pow(b, a)))
        print("a = ", a, ", n = ", n, ", m = ", m, ", ans = ", cnt)

输出:

a =  1 , n =  1 , m =  2 , ans =  1
a =  1 , n =  2 , m =  4 , ans =  1
a =  1 , n =  3 , m =  8 , ans =  1
a =  1 , n =  4 , m =  16 , ans =  1
a =  2 , n =  1 , m =  2 , ans =  1
a =  2 , n =  2 , m =  4 , ans =  2
a =  2 , n =  3 , m =  8 , ans =  3
a =  2 , n =  4 , m =  16 , ans =  5
a =  3 , n =  1 , m =  2 , ans =  1
a =  3 , n =  2 , m =  4 , ans =  1
a =  3 , n =  3 , m =  8 , ans =  1
a =  3 , n =  4 , m =  16 , ans =  1
a =  4 , n =  1 , m =  2 , ans =  1
a =  4 , n =  2 , m =  4 , ans =  2
a =  4 , n =  3 , m =  8 , ans =  4
a =  4 , n =  4 , m =  16 , ans =  8
a =  5 , n =  1 , m =  2 , ans =  1
a =  5 , n =  2 , m =  4 , ans =  1
a =  5 , n =  3 , m =  8 , ans =  1
a =  5 , n =  4 , m =  16 , ans =  1

打表只要注意别打错就好,这道题数量增长会很快,如果发现有个别数据规律比较奇怪,最好去验证一下,看看是不是因为精度问题得到的错误结果,如果打表打错了,岂不是很糟糕,规律基本就没办法找了。

打表可以发现,当a为奇数的时候,答案固定为1【证明比较长,篇幅大约1500多字,所以单独另写了一篇:关于对a^b % 2^n = b^a % 2^n,当a为奇数时,在范围[1, 2^n]有且仅有一个b使等式成立的证明】。当a不是奇数的时候(即a是偶数,可以表示为\(a = 2k\)),分类讨论一下,将问题简化,将b以n为分界【为什么要以n来分界呢?原因很简单,我们希望找到一些信息来减少枚举的计算量,n是个很好的值,因为:

\(a^b = (2k)^b = 2^bk^b\),

当b大于等于n的时候,\(a^b % m = 0\),在满足这个条件的时候,只要找到使\(b^a % m = 0\)成立的b的数量,这样即便是枚举都能够减少一些计算量,如果后面发现还可以推导出进一步的结论来简化计算(提前“剧透”:后面我们确实“很幸运地”推导出了更直接的解决方法),就可以更好地解决这个问题,因此取这个值很可能会对我们研究这个问题有帮助】。考虑到\(n \le 30\),当\(b < n\)的时候直接暴力枚举也不会有太大的消耗,我们对于\(b < n\)时采用暴力。接下来就是\(b \ge n\)的情形,这种情形,我们推测出满足的同余方程的b必然使\(b ^ a % m = 0\),由于a和m都是偶数,如果想让等式成立,b至少得是一个偶数【奇数的偶数次仍然是奇数,那样的话就必然不可能整除m】,更为具体的是\(b = 2 ^ t * y\)【简单说明一下,我们在表示b的时候将其因数2单独用\(2^t\)表示,剩下的因数全部用y来概括】,则有:

\(b^a = 2^{at} y^a\),

这个形式十分的友好,这个数中的因数2已经全部“聚集”到上式的\(2^{at}\)部分,显然可以判断出,如果让\(b^a % m = 0\)成立,只要\(at \ge n\)即\(t \ge n / a\),b的个数取决于t的个数和y的个数,为了找到n到m中有多少个符合条件的b,我们令\(t = ceil(n / a)\)【ceil是向上取整,如果向下取整的话会无法达成上面推出的整除条件】,之后把多余的因数2并入到y中,这样我们可以得到:

\(y = \frac{b}{2^{ceil(n / a)}}\)

当我们取b的取值上界\(b = m\)时,上式向下取整后得到的便是y的最大可取值(为了方便表述,记作\(y_{max}\)),y可以取\([1, y_{max}]\),这个范围内刚好有\(y_{max}\)个数,因此,这个值就是[1, m]中这样的b的个数,接着还需要处理一点,由于这个结论是建立在前提条件\(b \ge n\)下的,所以刚才的\(y_{max}\)还需要减去下界\(y_{min} = \frac{n}{2^{ceil(n / a)}}\)在加上枚举\(b \le n\)结果才是最后的答案。

AC代码如下:

#include <iostream>

using namespace std;

typedef long long LL;

LL pow(LL a, LL b, LL mod) {
    LL ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}

LL pow(LL a, LL b) {
    LL ret = 1;
    while (b) {
        if (b & 1) ret = ret * a;
        a = a * a;
        b >>= 1;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    LL a, n;
    while (cin >> n >> a) {
        if (a & 1) {
            cout << "1" << endl;
        } else {
            LL cnt = 0, m = 1 << n;
            for (LL b = 1; b <= n; b++)
                if (pow(a, b, m) == pow (b, a, m)) cnt++;
            LL tmp = 1 << ((n + a - 1) / a);
            cnt += m / tmp - n / tmp;
            cout << cnt << endl;
        }
    }
    return 0;
}

备注:上面的两个pow函数分别是快速模幂函数和快速幂函数。