## 【HDU-6189】Law of Commutation

【HDU-6189】Law of Commutation

Solution:

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^b = (2k)^b = 2^bk^b$$,

$$b^a = 2^{at} y^a$$,

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

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;
}