E-水题(water)

题目所求三个部分
1.斐波那契
2.n!在m进制下末尾零的个数
3.N皇后问题
前导
一：求n!中质因子p的个数
基于事实：n!的质因子p的个数等于：1~n中p的倍数(n/p)加上(n/p)!中质因子p的个数

递归代码：

ll getcnt(ll p, ll n) {
    if (n < p) return 0;
    return n / p + getcnt(p, n / p);
}

转换为非递归代码：

ll getcnt(ll p, ll n) { //求x!有几个p
    ll res(0);
    while (n) res += n / p, n /= p;
    return res;
}

二：求n!在m进制末尾零的个数

总代码如下

#pragma warning (disable :4996)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = cos(-1.0);
const double eps = 1e-10;
#define For(i,n,m) for(int i=n;i<=m;++i)

ll x, m;
ll d_cnt[108], a_cnt[108];
ll prime[] = { 0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 };
ll res[] = { 0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712 };
ll fi[108];
ll getcnt(ll p, ll x) { //求x!有几个质因数p
    ll res(0);
    while (x) res += x / p, x /= p;
    return res;
}
void m_solve() {
    ll mm(m), k(1e18);
    for (int i = 1; prime[i] <= mm; ++i) {
        while (mm % prime[i] == 0) ++a_cnt[prime[i]], mm /= prime[i];
    }
    for (int i = 1; i <= 25; ++i) {
        if (a_cnt[prime[i]]) d_cnt[prime[i]] = getcnt(prime[i], x);
    }
    for (int i = 1; i <= 25; ++i) {
        if (a_cnt[prime[i]]) k = min(k, d_cnt[prime[i]] / a_cnt[prime[i]]);
    }
    cout << k << "\n";
}
void z_solve() {
    ll z = x % (min(13ll, m)) + 1;
    cout << res[z] << "\n";
}
int main() {
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> x >> m;
    fi[1] = 1, fi[2] = 1;
    for (int i = 3;; ++i) {
        fi[i] = fi[i - 1] + fi[i - 2];
        if (fi[i] > 1e18) break;
    }
    bool f = false;
    for (int i = 1;; ++i) {
        if (fi[i] > 1e18) break;
        if (fi[i] == x) { f = true; break; }
    }
    if (f) m_solve();
    else z_solve();
    return 0;
}