旺崽的博客

要么天赋异禀，要么天道酬勤

0%

发表于 分类于 Valine：

题目链接

我们称一个分割整数数组的方案是 好的 ，当它满足：

数组被分成三个 非空 连续子数组，从左至右分别命名为 left ， mid ， right 。
left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。
给你一个 非负 整数数组 nums ，请你返回 好的 分割 nums 方案数目。由于答案可能会很大，请你将结果对 $10^9+7$ 取余后返回。

示例 1：

1
2
3
输入：nums = [1,1,1]
输出：1
解释：唯一一种好的分割方案是将 nums 分成 [1] [1] [1] 。

示例 2：

1
2
3
4
5
6
输入：nums = [1,2,2,2,5,0]
输出：3
解释：nums 总共有 3 种好的分割方案：
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]

示例 3：

1
2
3
输入：nums = [3,2,1]
输出：0
解释：没有好的分割方案。

题意比较简单，就是往一个数组里插两块隔板，暴力的话复杂度 $O(n^2)$，显然不行，考虑优化，很容易想到二分，遍历第一块隔板的位置 $i$，然后找第二块隔板的所有合法位置区间 $[L,R]$ 即可，预处理所有数的前缀和，左端点 $L$ 可以通过一个 $lower_bound$ 直接求得，而对右端点 $R$，直接二分求即可，对每一块隔板 $i$，答案加上 $R-L+1$，AC代码如下：

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
class Solution {
public:
    long long pre[100005] = {0}, ans = 0, mod = 1e9 + 7, len;
    vector<long long> v;
    
    int bs(int l, int r, int p) {
        while (l <= r) {
            int mid = l + r >> 1;
            if (pre[len - 1] - pre[mid] >= pre[mid] - pre[p]) l = mid + 1;
            else r = mid - 1;
        }
        return r;
    }

    int waysToSplit(vector<int> &nums) {
        len = nums.size();
        for (int i = 0; i < len; i++) {
            if (i == 0) pre[i] = nums[i];
            else pre[i] = pre[i - 1] + nums[i];
            v.push_back(pre[i]);
        }
        for (int i = 0; i < len - 2; i++) {
            int pos1 = lower_bound(v.begin() + i + 1, v.end(), pre[i] + pre[i]) - v.begin();
            if (pos1 == v.size()) break;
            int pos2 = bs(pos1, len - 2, i);
            ans = (ans + (long long) (pos2 - pos1 + 1)) % mod;
        }
        return ans;
    }
};

发表于 分类于 Valine：

题目链接

Consider all binary strings of length m (1≤m≤60). A binary string is a string that consists of the characters 0 and 1 only. For example, 0110 is a binary string, and 012aba is not. Obviously, there are exactly 2m such strings in total.

The string s is lexicographically smaller than the string t (both have the same length m) if in the first position i from the left in which they differ, we have s[i]<t[i]. This is exactly the way strings are compared in dictionaries and in most modern programming languages when comparing them in a standard way. For example, the string 01011 is lexicographically smaller than the string 01100, because the first two characters are the same, and the third character in the first string is less than that in the second.

We remove from this set $n (1≤n≤min(2^{m−1},100))$ distinct binary strings a1,a2,…,an, each of length m. Thus, the set will have k=2m−n strings. Sort all strings of the resulting set in lexicographical ascending order (as in the dictionary).

We number all the strings after sorting from 0 to k−1. Print the string whose index is ⌊k−1⌋/2 (such an element is called median), where ⌊x⌋ is the rounding of the number down to the nearest integer.

For example, if n=3, m=3 and a=[010, 111, 001], then after removing the strings ai and sorting, the result will take the form: [000, 011, 100, 101, 110]. Thus, the desired median is 100.

Input

The first line contains an integer t (1≤t≤1000) — the number of test cases. Then, t test cases follow.

The first line of each test case contains integers $n (1≤n≤min(2^{m−1},100))$ and m (1≤m≤60), where n is the number of strings to remove, and m is the length of binary strings. The next n lines contain a1,a2,…,an — distinct binary strings of length m.

The total length of all given binary strings in all test cases in one test does not exceed $10^5$.

Output

Print t answers to the test cases. For each test case, print a string of length m — the median of the sorted sequence of remaining strings in the corresponding test case.

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
5
3 3
010
001
111
4 3
000
111
100
011
1 1
1
1 1
0
3 2
00
01
10

output

1
2
3
4
5
100
010
0
1
11

这题用到了位运算，我们把所有二进制字符串转化为十进制存入数组 $a$，考虑到内存限制，$bitset$ 恰好完美地解决了这个问题，我们先定位要找的那个数的位置 $pos$，也即十进制里面的大小，然后遍历数组 $a$，如果有数小于等于 $pos$，则 $pos+1$，最后再将其转化为二进制输出即可，AC代码如下：

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
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    ll a[n];
    string s;
    ll ans = ((1LL << m) - n - 1) / 2;
    for (int i = 0; i < n; i++) {
        cin >> s;
        a[i] = bitset<64>(s).to_ullong();
    }
    sort(a, a + n);
    for (auto i:a) ans += (i <= ans);
    cout << bitset<64>(ans).to_string().substr(64 - m) << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
}

发表于 分类于 Valine：

题目链接

题目描述

广义肥波那契数列，以递归的方法定义如下：

$\begin{cases}f1=1\f_2=1\f_n=a\cdot f{n-1}+b\cdot f_{n-2}(n\ge 3, n\in \mathbb Z)\end{cases}$

例如，当 $a=b=\text 1$ 时，数列为 $[\text 1,1,2,3,5,8,13,…]$。
现在，请求出 $m^{f_n}$。

输入描述:

输入共一行,包含 $\text 4$ 个正整数 $a,b,m,n(1\le a,b,m\le 10^9,1\le n \le 10^5)$

输出描述:

输出共一行，包含一个非负整数表示答案。由于结果可能较大，你只需要输出答案对 $10^9+7=1,000,000,007$ 取模的结果。

示例1

输入

1
1 1 2 4

输出

1
8

求斐波那契数列就是简单的矩阵快速幂了，但是题目设了一个小坑，就是 $a^b\% mod$，显然你的幂数和底数的模数是不一样的，而 $mod=10^9+7$，模数恰为素数，所以根据欧拉降幂，$a^b\%mod=a^{b\%(mod-1)}\% mod$，很多人可能意识到了矩阵快速幂，但是忽略了这个，AC代码如下：

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
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll mod = 1e9 + 7, n, K, A, B, m, mod1 = 1e9 + 6;

ll power(ll a, ll b) { return b ? power(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }

struct mat {
    ll m[2][2];
};

mat mul(mat a, mat b) {
    mat c;
    memset(c.m, 0, sizeof(c.m));
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            if (a.m[i][k] == 0) continue;
            for (int j = 0; j < n; j++) {
                c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod1;
                if (c.m[i][j] < 0) c.m[i][j] += mod1;
            }
        }
    }
    return c;
}

mat mat_pow(mat a, int k) {
    mat ans;
    ans.m[0][0] = 1, ans.m[1][0] = 1;
    ans.m[0][1] = ans.m[1][1] = 0;
    while (k > 0) {
        if (k & 1) ans = mul(a, ans);
        a = mul(a, a);
        k >>= 1;
    }
    return ans;
}


int main() {
    n = 2;
    cin >> A >> B >> m >> K;
    mat a;
    a.m[0][0] = A, a.m[0][1] = B;
    a.m[1][0] = 1, a.m[1][1] = 0;
    if (K <= 2) cout << m;
    else {
        mat ans = mat_pow(a, K - 2);
        ll u = ans.m[0][0];
        cout << power(m, u);
    }
    return 0;
}

发表于 分类于 Valine：

题目链接

题目描述

算数基本定理，又称唯一分解定理，算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积。即 $N=p_1^{e_1}\cdot p_2^{e_2}…p_m^{e_m}(p_1 < p_2< … p_m)$ 朴素的质因子分解算法就是利用了算数基本定理，依次枚举 $p$ 判断N是否包含素因子 $p$。

牛牛最近对于质因数分解产生了浓厚的兴趣。

牛牛定义了一个函数 $F(x)$，它表示将 $x$ 做质因数分解后得到的数字从小到大升序排列，然后将其“拼接”成一个大整数。
例如 $1500=22355*5,F(1500)=223555$。
牛牛现在想要知道 $\sum_{i=2}^{n}F(i)$ 的值。

由于这个结果非常大，所以你只用告诉牛牛最终答案对 $10^9+7$ 取余数的结果即可。

输入描述:

仅一行一个正整数 $n(2 \leq n \leq 4 \times 10^6)$

输出描述:

仅一行，表示答案对 $10^9+7$ 取余数的结果。

示例1

输入

1
3

输出

1
5

示例2

输入

1
10

输出

1
342

一开始就想着暴力算，素筛+质因子分解，这样写跑 $4e6$ 本地要 $3$ 秒，自闭了一会儿我就去忙别的了，最后一个小时突然觉悟了，为什么不记忆化一下每一次算得的答案呢，比如我们暴力算 $20$ 的时候，要算出它所有的质因子:

1
2 2 5

而记忆化的时候我们只需要算 $2*10^{cnt[ans[10]]}+ans[10]$ 即可，什么意思呢？我们记忆化的时候存两个值，一个是 $ans$ (记录某个数算得的答案)，一个是 $cnt$ (记录某个数答案的位数)，我们只需要遍历一遍 $n$ 直接算出所有答案即可，递推公式如下:

为了方便计算我还是选了素筛，把 $j$ 替换成了素数，这样复杂度就是线性筛+一次遍历，一共 $O(2N)$，上面公式直接算也可以，复杂度稍高，应该是 $O(NlogN)$，AC代码如下：

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll N = 4e6 + 10;
const ll mod = 1e9 + 7;
ll n, k, sum, prime[N / 10], cnt[N], ans[N], vis, p10[1000];
bool isprime[N];

ll f(ll x) {
    ll num = 0;
    while (x) {
        num++;
        x /= 10;
    }
    return num;
}

void Prime() {
    fill(isprime, isprime + N, 1);
    k = 0;
    for (int i = 2; i <= N; i++) {
        if (isprime[i]) {
            prime[k++] = i;
        }
        for (int j = 0; j < k; j++) {
            if (i * prime[j] > N) break;
            isprime[i * prime[j]] = 0;
            if (i % prime[j] == 0) break;
        }
    }
}

void init() {
    p10[0] = 1;
    for (ll i = 1; i < 1000; i++) p10[i] = 10 * p10[i - 1] % mod;
}

int main() {
    cin >> n;
    init();
    Prime();
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < k; j++) {
            if (i * prime[j] > n) break;
            if (i == 1) {
                ans[prime[j]] = prime[j] % mod;
                cnt[prime[j]] = f(prime[j]);
                continue;
            }
            cnt[i * prime[j]] = cnt[i] + cnt[prime[j]];
            if (i < prime[j]) {
                ans[i * prime[j]] = (ans[i] * p10[cnt[prime[j]]] % mod + ans[prime[j]] % mod) % mod;
            } else ans[i * prime[j]] = (ans[prime[j]] * p10[cnt[i]] % mod + ans[i] % mod) % mod;
        }
    }
    for (int i = 2; i <= n; i++) {
        sum = (sum + ans[i]) % mod;
    }
    cout << sum << endl;
    return 0;
}

发表于 分类于 Valine：

题目链接

题目描述

输入一个数 $n$，请构造一个长度为 $n$ 的排列，使得其中正好有 $k$ 对相邻的数 $gcd$（最大公约数）大于 $1$ 。
排列是指 $1$ 到 $n$ 一共 $n$ 个数，每个数都出现过且仅出现过 $1$ 次。

输入描述:

两个整数 $n$ 和 $k$，用空格隔开。
$2\leq n\leq 100000,0\leq k \leq n/2$

输出描述:

如果不存在可行的构造方案，输出 $-1$。
否则输出一行 $n$ 个数，用空格隔开。如果有多组可行的构造方案，输出任意一组即可。

示例1

输入

1
2 1

输出

1
-1

示例2

输入

1
6 3

输出

1
5 3 6 2 4 1

题目限制了 $k\leq n/2$，这点非常关键，我就是没有意识到这一点卡了很久~
我们发现 $1-n$ 之间的偶数恰好是 $\frac{n}{2}$ 个，所以我们只需要排列这些偶数就能获得 $\frac{n}{2}-1$ 对，那么离最大目标还差一个，我们只需要抽一个 $6$ 出来和 $3$ 拼在一起就行，剩下的数按顺序输出即可，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    int n, k;
    vector<int> v;
    set<int> s;
    cin >> n >> k;
    if (n < 6 && k == n / 2) {
        cout << "-1";
        return 0;
    }
    for (int i = 2; i <= n; i += 2) if (i != 6) v.push_back(i);
    v.push_back(6);
    v.push_back(3);
    for (int i = 0; i <= k; i++) cout << v[i] << " ", s.insert(v[i]);
    for (int i = 1; i <= n; i++) if (!s.count(i)) cout << i << " ";
    return 0;
}

发表于 分类于 Valine：

题目链接

给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums（下标 从 0 开始 计数）：

  • nums.length == n
  • nums[i] 是 正整数 ，其中 0 <= i < n
  • abs(nums[i] - nums[i+1]) <= 1 ，其中 0 <= i < n-1
  • nums 中所有元素之和不超过 maxSum
  • nums[index] 的值被最大化

返回你所构造的数组中的 nums[index] 。

注意：abs(x) 等于 x 的前提是 x >= 0 ；否则，abs(x) 等于 -x 。

示例 1：

1
2
3
输入：n = 4, index = 2,  maxSum = 6
输出：2
解释：数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。

示例 2：

1
2
输入：n = 6, index = 1,  maxSum = 10
输出：3

一开始以为是找规律，还打表找了半天的规律，后来转念一想发现这不就是二分吗，我们只需要二分那个最大值，从它的下标往两边值递减即可，注意值最小是 1，另外对数列求和会爆 int，所以二分判断到时候要用 longlong，AC 代码如下：

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
class Solution {
public:
    bool check(long long x, long long y, long long z, long long n) {
        long long num1 = y, num2 = n - y - 1;
        long long sum1 = 0, sum2 = 0;
        if (num1 >= x - 1) {
            sum1 = (x - 1) * x / 2 + num1 - (x - 1);
        } else {
            sum1 = num1 * (x - num1 + x - 1) / 2;
        }
        if (num2 >= x - 1) {
            sum2 = (x - 1) * x / 2 + num2 - (x - 1);
        } else {
            sum2 = num2 * (x - num2 + x - 1) / 2;
        }
        return (sum1 + sum2 + x <= z);
    }

    int maxValue(int n, int index, int maxSum) {
        int l = 1, r = maxSum;
        while (l <= r) {
            int mid = l + r >> 1;
            if (check(mid, index, maxSum, n)) l = mid + 1;
            else r = mid - 1;
        }
        return r;
    }
};

发表于 分类于 Valine：

题目链接

题目描述

You are given a string $s{}$​ of $n{}$ lowercase letters.
You have to delete exactly two letters from $s{}$, determine whether the string can become a palindrome after the change.
Definition of palindrome: If a string $s{}$ of $n{}$ lowercase letters is a palindrome, then for each $s_i(1\leq i\leq n),s_i=s{n-i+1}$ .
For example, “ababa” and “abba” are palindromes, but “abab” not.

输入描述:

The first line contains an integer $t(1\leq t\leq10^3)$ — the number of test cases.
For each test case, the first line contains an integer $n(3\leq n\leq 2!\cdot!10^3)$ representing the length of $s{}$, the second line contains a string of length $n{}$.
It is guaranteed that the sum of $n{}$ for all test cases does not exceed $10^4{}$.

输出描述:

If it is possible to change the string into a palindrome after deleting two letters from $s_{}$, please output “Yes”, otherwise output “No”.

示例1

输入

1
2
3
4
5
6
7
3
4
abca
6
ababab
6
abcabc

输出

1
2
3
Yes
Yes
No

自己手写几个例子很容易发现修改不超过 2 次的能构成回文串的字符串都可以，简单说明一下：

  1. 本身是回文串，开头结尾各删一个即可
  2. 删掉一个字符构成回文串，此时的回文串不管长度是奇数还是偶数，删掉中间的那个字符还是回文串

所以我们只需要用 DFS 暴力删除即可，如果删除次数超过 2 返回 0，否则返回 1，在 DFS 的过程中维护两个指针即可，复杂度 $O(4*n)$，AC 代码如下：

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
#include "bits/stdc++.h"

using namespace std;
int n, t;
string s;

bool dfs(int l, int r, int cnt) {
    if (l >= r) return 1;
    else {
        if (s[l] != s[r]) {
            if (cnt == 0) return 0;
            if (cnt > 1) return dfs(l + 1, r, cnt - 1) || dfs(l, r - 1, cnt - 1) || dfs(l + 1, r - 1, cnt - 2);
            if (cnt > 0) return dfs(l + 1, r, cnt - 1) || dfs(l, r - 1, cnt - 1);
            return 0;
        } else return dfs(l + 1, r - 1, cnt);
    }
}

int main() {
    cin >> t;
    while (t--) {
        cin >> n >> s;
        if (dfs(0, n-1, 2)) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

发表于 分类于 Valine：

题目链接

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。

给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的最大平均通过率。与标准答案误差范围在 $10^{-5}$ 以内的结果都会视为正确结果。

示例 1：

1
2
3
输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2
输出：0.78333
解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。

示例 2：

1
2
输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出：0.53485

一开始想的是排序，后来发现变化是动态的，观察到 extraStudents 这个变量不大，那可以就用优先队列一个一个加，我们优先队列存每个班加一个学生之后提升的通过率，设为大根堆，每次对队头操作即可，AC 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    double maxAverageRatio(vector<vector<int>> &classes, int extraStudents) {
        priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, less<>> q;
        double sum = 0;
        for (auto &i:classes)
            sum += double(i[0]) / i[1], q.push({double(i[0] + 1) / (i[1] + 1) - double(i[0]) / i[1], i[0], i[1]});
        while (extraStudents) {
            extraStudents--;
            auto[a, b, c]=q.top();
            q.pop();
            sum += a;
            q.push({double(b + 2) / (c + 2) - double(b + 1) / (c + 1), b + 1, c + 1});
        }
        return sum / classes.size();
    }
};

发表于 分类于 Valine：

题目链接

当 A 的子数组 A[i], A[i+1], …, A[j] 满足下列条件时，我们称其为湍流子数组：

若 i <= k < j，当 k 为奇数时， A[k] > A[k+1]，且当 k 为偶数时，A[k] < A[k+1]；
或 若 i <= k < j，当 k 为偶数时，A[k] > A[k+1] ，且当 k 为奇数时， A[k] < A[k+1]。
也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。

返回 A 的最大湍流子数组的长度。

示例 1：

1
2
3
输入：[9,4,2,10,7,8,8,1,9]
输出：5
解释：(A[1] > A[2] < A[3] > A[4] < A[5])

示例 2：

1
2
输入：[4,8,12,16]
输出：2

示例 3：

1
2
输入：[100]
输出：1

思维~
官方题解有滑窗，有 DP，但是我另辟蹊径，用一种纯思维的方式，首先求两两数的差值，存入 diff 数组：

  • arr[i]>arr[i+1]，存入 $1$
  • arr[i]<arr[i+1]，存入 $-1$
  • arr[i]=arr[i+1]，存入 $0$

求得这个差值数组之后，我们就所有找的最大长度，无非就是求 $1,-1,\cdots,-1，1$ 序列的最大长度，设一个 $mx$ 变量维护最大值即可，对某一位置 $i$ 判断下面两种情况：

  • diff[i]=0，此时必须把 mx 置 0，因为差值为 0 时最大长度为 1
  • diff[i]≠0，若 diff[i]+diff[i+1]=0，mx++；若 diff[i]+diff[i+1]≠0，把 mx 置 1，因为差值不为 0 时的最大长度为 2

每次循环 ans=max(ans,mx+1)，因为 mx 个差值对应 mx+1 个数，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxTurbulenceSize(vector<int> &arr) {
        if (arr.size() == 1) return 1;
        vector<int> diff;
        for (int i = 0; i < arr.size() - 1; i++) {
            if (arr[i] > arr[i + 1]) diff.emplace_back(1);
            else if (arr[i] < arr[i + 1]) diff.emplace_back(-1);
            else diff.emplace_back(0);
        }
        int ans = (diff.front() ? 2 : 1), mx = (diff.front() ? 1 : 0);
        for (int i = 1; i < diff.size(); i++) {
            if (!diff[i]) mx = 0;
            else {
                if (diff[i] + diff[i - 1] == 0) mx++;
                else mx = 1;
            }
            ans = max(ans, mx + 1);
        }
        return ans;
    }
};

发表于 分类于 Valine：

题目链接

Problem Statement

Given are a string X consisting of 0 through 9, and an integer M.

Let d be the greatest digit in X.

How many different integers not greater than M can be obtained by choosing an integer n not less than d+1 and seeing X as a base-n number?

Sample Input 1

1
2
22
10

Sample Output 1

1
2

Sample Input 2

1
2
999
1500

Sample Output 2

1
3

Sample Input 3

1
2
100000000000000000000000000000000000000000000000000000000000
1000000000000000000

Sample Output 3

1
1

思维+二分~
题意很简单，就是找最大的 n-进制，使得该进制下的 $X \leq M$，很容易想到二分，二分这个最大进制数即可，判断也很好判断，就是模拟 n-进制转十进制，一旦模拟的过程中大于 $M$，立即跳出即可~
这题最大的一个坑点在于 $X$ 只有一位的时候，此时任意进制下的 $X$ 都相等，所以只需要判断 $X$ 和 $M$ 的大小即可。我害怕二分模拟的过程中爆 long long，所以用 py 写的，AC 代码如下：

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
import sys

x = input()
m = int(input())
if len(x) == 1:
    if int(x) <= m:
        print(1)
    else:
        print(0)
    sys.exit(0)
len = len(x)


def check(n):
    sum = 0
    for j in range(0, len):
        ss = 1
        for k in range(0, len - j - 1):
            ss *= n
            if ss > m:
                return 1
        sum += ss * (ord(x[j]) - ord('0'))
        if sum > m:
            return 1
    return 0


d = 0
ans = 0
for i in x:
    d = max(d, ord(i) - ord('0') + 1)

l = d
r = 10 ** 18 + 1
while l <= r:
    mid = (l + r) // 2
    if check(mid):
        r = mid - 1
    else:
        l = mid + 1
print(r - d + 1)