标签 数学 下的文章

url: http://oj.ecustacm.cn/problem.php?id=1361

tag:
数学

思路：
计算末尾零可以求每个因子中有多少对因子5和因子2，因为2 * 5 = 10，又因为2出现的次数会比5多，因为只要是偶数的情况就会出现因子2.所以只要计算这100个数中，每个数中因子5的个数，然后累加最后输出即可。

对于求阶乘来说，如果是某个数的阶乘，求这个数除以5，25，125……5k之后累加。例如100除以5之后等于20，那么对于1到20来说每个数乘以5后都会变成一个贡献5因子的数，除以25之后等于4说明1到4中每个数乘25都可以变成一个贡献25因子的数，而25 = 5 5，则是在原来贡献了5因子基础上多贡献一个5，为了避免重复，以及避免漏算，只需要将4 加上 20，即为答案。说明对于100！（1 2 3 …… * 100）来说，一共可以贡献出24个因子5，就是有24个末尾0.这种求阶乘末尾0的方式实际上和本题有出路。

代码：

// 乘积尾零
#include <iostream>
using namespace std;
int main()
{
    int n = 10;
    int cnt = 0;
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < n; j ++)
        {
            int a;
            cin >> a;
            while (a && a % 5 == 0)
            {
                if (a % 5 == 0)
                {
                    a /= 5;
                    cnt ++;
                }
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

答案：

#include <iostream>
using namespace std;
int main()
{
    cout << 31 << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/B3738

tag：
模拟，数学

思路：
数据范围比较小，可以用模拟的方式来通过这道题。比较难的部分应该是蛇形填充。这里可以先用一个数组来存放四个前进的方向。之后每次都判断一下前进之后的位置符不符合要求（不越界且当前位置没有被填充过），如果符合要求则前进，然后将数字放进矩阵，否则就换一个方向。

代码：

#include <iostream>
using namespace std;
int n, x, y;
const int N = 22;
int p[410], dp[N][N], d;
int dir[4][2] = {
        {0, 1},
        {1, 0},
        {0, -1},
        {-1, 0},
};
bool is_pr(int x)
{
    for (int i = 2; i * i <= x; i ++)
    {
        if (x % i == 0) return false;
    }
    return true;
}
int main()
{
    cin >> n >> x >> y;
    int k = 2;
    for (int i = 1; i <= n * n; i ++)
    {
        while (!is_pr(k++));
        p[i] = --k;
        k ++;
    }
    int nx = 0, ny = 0;
    dp[0][0] = p[1];
    for (int i = 2; i <= n * n; i ++)
    {
        int tmpx, tmpy;
        tmpx = nx + dir[d][0], tmpy = ny + dir[d][1];
        if (tmpx >= n || tmpx < 0 || tmpy >= n || tmpy < 0 || dp[tmpx][tmpy])
        {
            d = (d + 1) % 4;
            tmpx = nx + dir[d][0], tmpy = ny + dir[d][1];
        }
        nx = tmpx, ny = tmpy;
        dp[nx][ny] = p[i];
    }
    cout << dp[x - 1][y  - 1] << endl;
    return 0;
}