题解 - [Luogu P4861] 按钮 (aka 模板 - 阶)

发表于 更新于 分类于 ， 本文字数： 383 阅读时长 ≈ 1 分钟

题目链接

原始题面

题目背景

Ada 被关在了一个房间里

题目描述

房间的铁门上有一个按钮，还有一个显示屏显示着 "1"

旁边还有一行小字: "这是一个高精度 M 进制计算器，每按一次按钮，屏幕上的数便会乘以 K. 当个位数再次变为 1 时，门就开了."

由于 Ada 急于出去，所以你要在 1s 之内求出她的最小按键次数

输入输出格式

输入格式

一行，两个整数 M 和 K

输出格式

一行一个数字，表示最小按键次数。如果无论 Ada 按多少次都无法让门打开，输出 "Let's go Blue Jays!" (不含引号)

输入输出样例

输入样例 #1

1
11 2

输出样例 #1

1
10

输入样例 #2

1
6 26

输出样例 #2

1
Let's go Blue Jays!

说明

对于 30% 的数据，\(2\leq M,K\leq10^4\)

对于 100% 的数据，\(2\leq M,K\leq2\times 10^{9}\)

update: 我们不认为个位为 11,21,... 为问题的解 (例如，11 在 16 进制下记为 B)

解题思路

即求 \(\operatorname{ord}_m(k)\), 可以用扩展 BSGS 或暴力，此处选用暴力做法

时间复杂度

\[ \begin{aligned} \Theta\Bigg(\sqrt{K}+\sum_{d\mid\varphi(K);~d\leqslant\sqrt{\varphi(K)}}\log\varphi(K)\Bigg)&=O\left(\sqrt{K}+\frac{\varphi(K)-\varphi(\varphi(K))}{2}\log\varphi(K)\right)\\ &=O\left(\sqrt{K}+\sqrt{\varphi(K)}\log\varphi(K)\right) \end{aligned} \]

代码参考

Show code

Luogu_P4861view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
i64 qpow(i64 a, i64 b, i64 mod) {
  i64 res = 1;
  for (; b; b >>= 1, a = a * a % mod)
    if (b & 1) res = res * a % mod;
  return res;
}
i64 phi(i64 n) {
  i64 ans = n;
  for (int i = 2; i <= sqrt(n); ++i)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}
int main() {
  i64 m, k;
  cin >> m >> k;
  if (__gcd(m, k) > 1) {
    cout << "Let's go Blue Jays!" << endl;
    return 0;
  }
  i64 phim = phi(m);
  i64 ans = INT64_MAX;
  for (i64 i = 1; i <= sqrt(phim); ++i)
    if (phim % i == 0) {
      if (qpow(k, i, m) == 1) {
        ans = min(ans, i);
        break;
      } else if (qpow(k, phim / i, m) == 1) ans = min(ans, phim / i);
    }
  cout << ans;
}