数学专题-练习题

题目链接#

编号 #

题意#

$N$ 个数，每个数介于 $1$ 和 $M_i$ 之间（可以为 $1$ 或 $M_i$ ）。对于每一个 $M_i$ 选择一个数这个数在 $1$ 到 $M_i$ 之间，且选择的数不能重复。问一共有多少选择方案。

题解#

从小到大排序后，假设当前你对前i个进行了选择，这 $i$ 个选择的范围在 $1$ 到 $M_i$ 之间，对于第 $M_{i+1}$ 个数它之中一定有 $i$ 个数已经被选择过了，因为已经从小到大排过序了。所以对于每个 $M_i$ ,它对答案的贡献是使答案乘上 $M_i - i - 1$ 的结果。所以当 $M_i < i - 1$ 时是无解的。

代码#

1
#include<bits/stdc++.h>
2

3
using namespace std;
4

5
#define int long long
6
const int mod = 1e9 + 7;
7
void sl(){
8
    int n;
9
    cin >> n;
10
    vector<int> a(n + 1);
11
    for(int i = 1 ;i <= n ;i++){
12
        cin >> a[i];
13
    }
14
    sort(a.begin() + 1,a.end());
15
    int sum = 1;
16
    for(int i = 1 ;i <= n ;i++){
17
        if(a[i] < i){
18
            sum = 0;
19
            break;
20
        }
21
        sum = sum * (a[i] - i + 1) % mod;
22
    }
23
    cout << sum << '\n';
24
}
25
signed main(){
26
    ios::sync_with_stdio(false);
27
    cin.tie(0);
28
    cout.tie(0);
29
    int t = 1;
30
    // cin >> t;
31
    while(t--) sl();
32
    return 0;
33
}

小车问题 #

题意#

$A B$ 两地的距离 $s$ ，初始两人在 $A$ 地，人的步行速度 $a$ 和车的速度 $b$ ，车一次只能载一人求两人同时到达 $B$ 的所花费的最少时间。保证车速大于人的速度。

题解#

假设先开车带一个人行驶了 $x$ 距离，然后折返回去接第二个人，一路开到 $B$ 点，且保证两人同时到达，由此可列出方程：

(s - x) / a = 2 * (2 * x / (a + b) - x / b) + (s - x) / b \\ x = (b + a) * s / (b + 3 * a)

根据 $x$ 可求出最后时间为： $x / b + (s - x) / a$

代码#

1
#include<bits/stdc++.h>
2

3
using namespace std;
4

5
#define int long long
6

7
void sl(){
8
    double s,a,b;
9
    cin >> s >> a >> b;
10
    double x = (b + a) * s / (b + 3 * a);
11
    double t = x / b + (s - x) / a;
12
    cout << fixed << setprecision(6) << t << '\n';
13
}
14
signed main(){
15
    ios::sync_with_stdio(false);
16
    cin.tie(0);
17
    cout.tie(0);
18
    int t = 1;
19
    // cin >> t;
20
    while(t--) sl();
21
    return 0;
22
}

小凯的数字 #

题意#

$Q$ 次询问，每次询问给一个 $l$ 和 $r$ ，求出

\overline{l(l+1)(l+2)...(r-1)r}\mod 9

后的结果。

题解#

首先观察数据范围，发现询问次数在 $10^4$ 次，每次的询问范围在 $10^{12}$ 。因此可以判断该题应该是一道 $O(1)$ 的结论题。

首先观察 $7 \mod 9$ ， $70 \mod 9$ ， $700 \mod 9$ 等等，发现结果都是 $7$ 。因此可以大胆假设对于任意整数 $x$ ，有 $x \mod 9 = (x \times 10^y) \mod 9$ （其中 $y$ 为 $0$ 到正无穷之间的整数）。

而对于 $l$ 到 $r$ 拼接起来形成的巨大数，可以看做 $l \times 10^{y_l} + (l + 1) \times 10^{y_{l + 1}} + \ldots + r \times 10^{y_r}$ 。根据之前的假设，将 $10$ 的上标全部置为 $0$ 在 $x\mod 9$ 意义下的结果是一样的，所以原式变为 $l + (l + 1) + \ldots + r = \frac{(r - l + 1) \times (l + r)}{2}$ 。

因为我们最后需要对答案取模，为了防止取模后奇偶性发生改变，我们需要对 $(r - l + 1)$ 或者 $(l + r)$ 单独除 $2$

代码#

1
#include<bits/stdc++.h>
2

3
using namespace std;
4

5
#define int long long
6
const int mod = 9;
7

8
void sl(){
9
    int l,r;
10
    cin >> l >> r;
11
    int sum;
12
    if((l + r) % 2 == 0){
13
        sum = (((l + r) / 2 % mod) * ((r - l + 1) % mod)) % mod;
14
    }else{
15
        sum = (((l + r) % mod) * ((r - l + 1) / 2 % mod)) % mod;
16
    }
17
    cout << sum << '\n';
18
}
19
signed main(){
20
    ios::sync_with_stdio(false);
21
    cin.tie(0);
22
    cout.tie(0);
23
    int t = 1;
24
    cin >> t;
25
    while(t--) sl();
26
    return 0;
27
}

平均数 #

题意#

给一个长度为 $n$ 的数列，我们需要找出该数列的一个连续子串，使得该子串平均数最大化，并且子串长度 $\ge m$ 。

题解#

我们使用二分答案来解决这个问题。对于当前二分出的平均值，我们要确定它的合法性，可以通过以下步骤实现：

将所有数先减去平均值。
这时我们相当于是要找到一段区间，使得它的和大于 $0$
对减后的数组进行前缀和计算。
假设我们当前找到了 pre[i]，只需要判断 pre[1] 到 pre[i - m] 之间的最小值是否小于 pre[i]，就可以判断出是否存在这样的区间。

代码#

1
#include<bits/stdc++.h>
2

3
using namespace std;
4

5
#define int long long
6
void sl(){
7
    int n,m;
8
    cin >> n >> m;
9
    vector<int> a(n + 1);
10
    for(int i = 1 ;i <= n ;i ++){
11
        cin >> a[i];
12
        a[i] *= 10000;
13
    }
14
    auto check=[&](int x){
15
        vector<int> b = a,pre(n + 1);
16
        int mn = 0;
17
        for(int i = 1 ;i <= n ;i++){
18
            b[i] -= x;
19
            pre[i] = pre[i - 1] + b[i];
20
            if(i >= m){
21
                mn = min(mn,pre[i - m]);
22
                if(pre[i] > mn) return 1;
23
            }
24
        }
25
        return 0;
26
    };
27
    int l = 0,r = 30000000;
28
    while(l <= r){
29
        int mid = (l + r) >> 1;
30
        if(check(mid)) l = mid + 1;
31
        else r = mid - 1;
32
    }
33
    cout << l / 10 << '\n';
34
}
35
signed main(){
36
    ios::sync_with_stdio(false);
37
    cin.tie(0);
38
    cout.tie(0);
39
    int t = 1;
40
    // cin >> t;
41
    while(t--) sl();
42
    return 0;
43
}

Modified GCD #

题意#

有 $q$ 组询问，每次询问 $a,b$ 在 $[l,r]$ 之间的最大公约数，如果不存在输出 $-1$

题解#

首先考虑 $a, b$ 的最大公约数 $\gcd(a, b)$ 与 $a, b$ 其他公约数之间的关系，可以发现 $a, b$ 的所有公约数均是最大公约数的因数。因此我们先处理出最大公约数的所有因数，然后对于每次询问的 $l, r$ 进行二分查找即可。

代码#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
#define int long long
5

6
void sl( ){
7
    int a,b,q;
8
    cin >> a >> b >> q;
9
    int gd = __gcd(a,b);
10
    set<int> p;
11
    for(int i = 1 ;i * i <= gd ;i ++){
12
        if(gd % i == 0){
13
            p.insert(i);
14
            p.insert(gd / i);
15
        }
16
    }
17
    while(q--){
18
        int l,r;
19
        cin >> l >> r;
20
        if(gd < l){
21
            cout << "-1\n";
22
            continue;
23
        }
24
        if(gd <= r){
25
            cout << gd << '\n';
26
            continue;
27
        }
28
        auto it = p.upper_bound(r);
29
        it--;
30
        if(*it < l) cout << "-1\n";
31
        else cout << *it << '\n';
32
    }
33
}
34

35
signed main( ){
36
    ios::sync_with_stdio(false);
37
    cin.tie(0);
38
    cout.tie(0);
39
    int t = 1;
40
    //  cin>>t;
41
    while(t--) sl();
42
    return 0;
43
}

细胞分裂 #

题意#

给你 $m_1$ 与 $m_2$ ，并且给你 $n$ 个数，假设第 $i$ 个数为 $S_i$ ，找到最小的 $k$ 使得， $S_i ^ {k} \mod m_1^{m_2} = 0$ ，如果不存在这样的 $k$ ，输出 $-1$

题解#

首先我们需要知道两个结论：

$x \mod y = 0$ ，将 $x$ 和 $y$ 质因数分解后， $s1$ 为 $x$ 的质因数集， $s2$ 为 $y$ 的质因数集，那么 $s2$ 为 $s1$ 的一个子集。
假设 $z$ 是 $x$ 的一个质因数， $x$ 可以分解出 $num_z$ 个 $z$ ，而 $x^y$ 可以分解出 $num_z \times y$ 个 $z$ 。

之后我们在回来看题目，要保证 $S_i^k \mod m_1^{m_2} = 0$ ，可以先对 $m_1$ 进行质因数分解，并且对于每一个 $S_i$ 同样进行质因数分解。如果 $S_i$ 可以通过幂次操作使得取模结果为 0，那么 $m_1$ 的每一个质因数也需要在 $S_i$ 中出现，并且操作之后的每一个质因数的数量也要大于 $m_1$ 的每一个质因数的数量乘上 $m_2$

代码#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
#define int long long
5
const int N = 3e4 + 10;
6

7
vector<int> prime;
8
bool is[N];
9

10
void init(){
11
  for(int i = 2 ;i < N ;i ++){
12
    if(!is[i]){
13
      prime.push_back(i);
14
        for(int j = i * i ;j < N ;j += i){
15
        is[j] = 1;
16
      }
17
    }
18
  }
19
}
20

21
void sl( ){
22
  int m1,m2,n;
23
  cin >> n >> m1 >> m2;
24
  vector<int> a(n + 1);
25
  map<int,int> mp;
26
  int idx = 0;
27
  while(m1 > 1){
28
    while(m1 % prime[idx] == 0){
29
      mp[prime[idx]] ++;
30
      m1 /= prime[idx];
31
    }
32
    idx++;
33
  }
34
  for(auto it : mp){
35
    auto[u,v] = it;
36
    mp[u] *= m2;
37
  }
38
  int f = 0,num = -1;
39
  for(int i = 1 ;i <= n ;i ++){
40
    cin >> a[i];
41
  }
42
  for(int i = 1 ;i <= n ;i++){
43
    int flag = 1,mn = 0;
44
    for(auto x : mp){
45
      if(a[i] % x.first != 0){
46
        flag = 0;
47
        break;
48
      }
49
      int ans = 0;
50
      while(a[i] % x.first == 0){
51
        a[i] /= x.first;
52
        ans++;
53
      }
54
      mn = max(mn,(x.second - 1) / ans + 1);
55
    }
56
    if(flag == 0) continue;
57
    if(num == -1){
58
      num = mn;
59
    }else{
60
      num = min(num,mn);
61
    }
62
  }
63
  cout << num << '\n';
64
}
65

66

67
signed main( ){
68
  ios::sync_with_stdio(false);
69
  cin.tie(0);
70
  cout.tie(0);
71
  init();
72
  int t = 1;
73
//  cin>>t;
74
  while(t--) sl();
75
  return 0;
76
}

题目链接#

编号#

题意#

题解#

代码#

小车问题#

题意#

题解#

代码#

小凯的数字#

题意#

题解#

代码#

平均数#

题意#

题解#

代码#

Modified GCD#

题意#

题解#

代码#

细胞分裂#

题意#

题解#

代码#