2019牛客暑期NOIP真题班普及组7-数学

1. 麦森数

来源：NOIP2003提高组 https://ac.nowcoder.com/acm/contest/231/D

算法知识点: 高精度,快速幂,数学

复杂度：

解题思路：

首先考虑如何求位数。

我们发现在 之间的数均有 位。因此对于任意正整数 ，它的位数是 。

而由于2的整次幂的末位数字不为0，因此 的位数和 的位数相同，所以 的位数是 。

cmath库中有函数 log10()，直接使用即可。

然后考虑如何求最后500位数。

1. 直接乘 次，时间复杂度是
2. 用快速幂，时间复杂度是

因此我们选择第二种方法。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 510;

int a[N], c[N], res[N];

void mul(int a[N], int b[N], int res[N])
{
    memset(c, 0, N * 4);
    for (int i = 0; i < 500; i ++ )
        for (int j = 0; j < 500; j ++ )
            if (i + j < 500)
                c[i + j] += a[i] * b[j];
    for (int i = 0, t = 0; i < 500; i ++ )
    {
        t += c[i];
        res[i] = t % 10;
        t /= 10;
    }
}

void qmi(int p)
{
    res[0] = 1;
    a[0] = 2;
    while (p)
    {
        if (p & 1) mul(a, res, res);
        mul(a, a, a);
        p >>= 1;
    }
    res[0] -- ;
}


int main()
{
    int p;
    scanf("%d", &p);
    printf("%d\n", int(log10(2) * p) + 1);

    qmi(p);
    for (int i = 499, j = 0; j < 10; j ++ )
    {
        for (int k = 0; k < 50; k ++, i -- )
            printf("%d", res[i]);
        puts("");
    }
    return 0;
}

2. 循环

来源：NOIP2005提高组 https://ac.nowcoder.com/acm/contest/233/D

算法知识点: 高精度,数学,数论,递推

复杂度：

解题思路：

引理1： 前 位的所有循环节长度，一定是 前 位循环节长度的子集。

证明：

• 如果前 位都不相同，那么前 位一定也不相同。

引理2： 假设最小循环节长度是 ，那么所有循环节长度一定都是 的整数倍。

证明：

• 假设有循环节长度 不是 的倍数，那么 也一定是循环节，且 ，和 是最小循环节长度矛盾。

因此我们可以从小到大一位一位递推出前 位的循环节长度。

假设已经求出前 位的循环节长度 ，那当我们求前 位的循环节长度时，
只需枚举 是否和 相同即可。

注意这里只需要枚举前10项，因为前 位是固定不变的，只有第 位会变化，因此最多只有10种不同选择。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int nums[N], power[N], prod[N], npower[N];

void mul(int res[], int a[], int b[])
{
    static int c[N];
    memset(c, 0, sizeof c);
    for (int i = 0; i < m; i ++ )
        for (int j = 0; j < m; j ++ )
            c[i + j] += a[i] * b[j];
    for (int i = 0, t = 0; i < m; i ++ )
    {
        t += c[i];
        res[i] = t % 10;
        t /= 10;
    }
}

bool check_eq(int a[], int b[], int k)
{
    for (int i = 0; i < k; i ++ )
        if (a[i] != b[i])
            return false;
    return true;
}

int main()
{
    string number;
    cin >> number >> m;
    n = number.size();
    for (int i = 0, j = n - 1; i < min(n, m); i ++, j -- ) nums[i] = number[j] - '0';

    memcpy(power, nums, sizeof nums);

    int per[N] = {1};

    for (int k = 1; k <= m; k ++ )
    {
        int r = 0;
        memcpy(prod, nums, sizeof nums);
        memset(npower, 0, sizeof npower);
        npower[0] = 1;
        while (true)
        {
            mul(prod, prod, power);
            mul(npower, npower, power);
            r ++ ;
            if (check_eq(prod, nums, k)) break;
            if (r > 10) break;
        }
        if (r > 10)
        {
            per[0] = -1;
            puts("-1");
            break;
        }

        for (int i = 0, t = 0; i < N; i ++ )
        {
            t += per[i] * r;
            per[i] = t % 10;
            t /= 10;
        }
        memcpy(power, npower, sizeof power);
    }

    if (per[0] != -1)
    {
        int k = N - 1;
        while (!per[k]) k -- ;
        while (k >= 0) printf("%d", per[k -- ]);
    }
    return 0;
}

3. 数列

来源：NOIP2006提高组 https://ac.nowcoder.com/acm/contest/234/C

算法知识点: 数学,二进制,位运算

复杂度：

解题思路：

引理：当 时，。

证明：对 由数学归纳法可证。

• 假设当 时是正确的，那么当 时:
  • 

接下来将序列中的每个数，唯一映射到一个二进制数：

• 如果第 个方幂存在，则二进制数的第 位为1，否则为0。

由上述引理，序列中任意两数的大小关系，和映射成二进制数后的大小关系相同。
因此我们可以先求出第 个二进制数，然后再反射出原数即可。

C++ 代码：

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

LL get(int a, int b)
{
    LL res = 1;
    while (b -- ) res *= a;
    return res;
}

int main()
{
    int n, k;
    cin >> k >> n;

    LL res = 0;
    for (int i = 0; i < 20; i ++ )
        if (n >> i & 1)
            res += get(k, i);

    cout << res << endl;

    return 0;
}

4. 魔法阵

来源：NOIP2016提高组 https://ac.nowcoder.com/acm/contest/244/A

算法知识点: 前缀和,数学,组合计数,乘法原理,加法原理

复杂度：

解题思路：

一个魔法阵如下所示：

A和B之间的距离是2t，B和C之间的距离是6t+k，C和D之间的距离是t，其中t, k均为正整数。

左边红色部分框出的A和B是绑定的，右边绿色部分框出的C和D也是绑定的。
因此整个系统共有三个自由度：t、红色部分、绿色部分。

同时枚举三个自由度的计算量过大。在1秒内，我们只能枚举其中两个自由度。

首先枚举t。接下来并列枚举绿色部分和红色部分：

• 从左到右枚举绿色部分，当绿色部分固定后，则C应该累加的次数是所有满足要求的A和B的 cnt[A] * cnt[B] 的和，再乘以cnt[D]。其中cnt[A], cnt[B], cnt[D]是A, B, D出现的次数。所有满足要求的A和B就是整个线段左边的某个前缀，因此可以利用前缀和算法来加速计算。cnt[D]同理可得。
• 从右到左枚举红色部分可做类似处理。

参考文献

NOIP2016T4 魔法阵。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 15010, M = 40010;

int n, m;
int cnt[N];
int a[N], b[N], c[N], d[N], x[M];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i ++ )
    {
        scanf("%d", &x[i]);
        cnt[x[i]] ++ ;
    }

    for (int t = 1; t * 9 + 2 <= n; t ++ )
    {
        int sum = 0;
        for (int D = t * 9 + 2; D <= n; D ++ )
        {
            int A = D - t * 9 - 1;
            int B = A + t * 2;
            int C = D - t;
            sum += cnt[A] * cnt[B];
            c[C] += sum * cnt[D];
            d[D] += sum * cnt[C];
        }
        sum = 0;
        for (int A = n - t * 9 - 1; A; A -- )
        {
            int B = A + t * 2;
            int D = A + t * 9 + 1;
            int C = D - t;
            sum += cnt[C] * cnt[D];
            a[A] += sum * cnt[B];
            b[B] += sum * cnt[A];
        }
    }

    for (int i = 1; i <= m; i ++ ) printf("%d %d %d %d\n", a[x[i]], b[x[i]], c[x[i]], d[x[i]]);
    return 0;
}

 
另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ