牛客小白月赛 5 C. 水题(water)

发表于 分类于

链接

https://ac.nowcoder.com/acm/contest/135/C

题意

存在一个函数 $f(n),n \in \mathbb{N}^{*}$，且这个函数满足下面的一个关系：

$\sum\limits_{i=1}^{n}{f(i)^2}=f(n) \times f(n+1)$

对于一个正整数 $x$，若存在一个数 $k \in \mathbb{N}^{*}$，使得 $f(k)=x$，则求出 $x$的阶乘在 $m$ 进制下的末尾 $0$ 的个数；若不满足上述条件，输出 $z(z=x%\min(13,m)+1)$皇后的方案数

思路

打表可得 $f(n)$ 是斐波那契数列

若 $x$ 是斐波那契数列中的一项：

若 $x!$ 在 $m$ 进制下的末尾有 $k$ 个 $0$，那么 $x!$ 一定是 $m^k$ 的倍数

假设 $m=p_1^{a_1}*p_2^{a_2}\dotsp_k^{a_k}$

对于每个 $p_i^{a_i}$，我们只要求出 $x!$ 中有几个 $p_i^{a_i}$，取最小值即可

若 $x$ 不是斐波那契数列中的一项：

将z皇后方案数打表即可

代码

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
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pii;
const int q[]={-1,1,0,0,2,10,4,40,92,352,724,2680,14200,73712};
ll f[100];
vector<pii>pf;
int cnt;
void get_f() {
    f[1]=f[2]=1;
    for(int i=3;;i++) {
        f[i]=f[i-1]+f[i-2];
            if(f[i]>1e18){cnt=i;break;}
    }
}
ll calc(ll x,ll y,ll tot) {
    ll t=0;
    while(x) t+=x/y,x/=y;
    return t/tot;
}
ll solve(ll x,ll m) {
    ll res=1e18;
    for(ll i=2;i*i<=m;i++) {
        ll tot=0;
        if(m%i==0) {
        while(m%i==0) tot++,m/=i;
        res=min(res,calc(x,i,tot));
    }
    }
    if(m>1) res=min(res,calc(x,m,1));
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    get_f();
    ll x,m;
    cin>>x>>m;
    for(int i=1;i<=cnt;i++) if(f[i]==x){cout<<solve(x,m)<<endl;return 0;}
    cout<<q[x%min(m,13ll)+1]<<endl;
    return 0;
}