牛客算法周周练2 E水题(water) 题解

最让我痛苦的一道题，查错n久，结果发现数组开小了（？？？）

这道题其实相当于三道题的杂糅版

我们先来考虑第一道（选支）：

判断是否存在k使得 $f(k)=x$

注意到，x<=1e18

而根据f的递推式，f的上升很快，所以，对于f，我们可以直接暴力计算：

$f(n)=\frac{sum_{i=1}^{n-1}f(i)^2}{f(n-1)}$

当然，我查错的时候，怀疑我计算有锅，于是打表发现，这玩意儿就是菲波拉契数列，所以不管你直接模拟 $O(n^2)$ 递推还是菲波拉契 $O(n)$ 递推都可以，因为在n很小的时候f(n)就会大于1e18

现在，判断x是否在数列中还不简单嘛，直接枚举看看就行了，2333

然后我们来看看第二道：

求x!的m进制的末尾0个数

我们来回忆一下，将一个数x转化为m进制的代码：

while(x){
    num[++cnt]=x%m,x/=m;
}

然后转化过后，就是将num数组倒序输出后的结果，所以末尾0个数x就一定满足num[1-x]=0，且num[x+1]!=0

那么，我们假如求x转化m进制后末尾0个数的话，就可以这么写：

while(x%m==0){
    ++ans;x/=m;
}

等价于，x是 $m^{ans}$ 的倍数，且x不是 $m^{ans+1}$ 的倍数

那么，我们再回来看看这道题怎么做

我们是要求x!最多可以分解出多少个m

我们假设m= $p_1^{a_1}*p_2^{a_2}...p_k^{a_k}$

我们可以轻松求出x!最多可以分解出多少个 $p_i$ ，方法如下：

tot=(1-x)中 $p_i$ 的倍数的个数+ $p_i^2$ 的倍数的个数+...+ $p_i^k$ 的倍数的个数，如果枚举到 $p_i^t$ 的个数为0( $p_i^k>x$ )时，之后就可以不算了,可以证明，个数在log级别

当然，1-x中y的倍数的个数就是 $[\frac{x}{y}]$ ,这个结论很简单就不再加以阐释。

所以，总的来说，我们就可以logn求出x!最多可以分解出多少个 $p_i$ ，设 $tot_i$

那么，最多可以分解出 $p_i^{a_i}$ 的个数就是 $[\frac{tot_i}{a_i}]$

所有上述值取最小就是我们要的答案了

update:加个解释：

设 $ci=[\frac{tot_i}{a_i}]$

我们要凑出m，需要1个 $p_1$ ,1个 $p_2$ ...1个 $p_k$ ,而两两之间不能转换（因为都是质数）

现在，你要 $c_1$ 个 $p_1$ , $c_2$ 个 $p_2$ ... $c_k$ 个 $p_k$ ,问你最多能凑出多少个m

答案明显就是 $min(c_i)$ 了

再看看第三道问题

求z皇后方案数

注意到，z的生成是：

(z=x%min(13,m)+1)

所以z的范围为1-13

所以，我们可以打个dfs直接跑

然而，只有13个，干嘛浪费时间打dfs呢？

直接打个表不就完了？23333

代码（由于查错的时候以为爆long long了，全开的__int128...）：

#include<bits/stdc++.h>
using namespace std;
const int N=501;
__int128 f[N];
__int128 res[N]={0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712};
inline __int128 read(){
    char ch=getchar();__int128 w=0,ss=0;
    while(ch<'0'||ch>'9')w|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')ss=(ss*10+(ch-'0')),ch=getchar();
    return w?-ss:ss;
}
inline void write(__int128 x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(char(x%10+'0'));
}
inline __int128 min(__int128 x,__int128 y){
    return x<y?x:y;
}
inline __int128 calc(__int128 x,__int128 y){
    __int128 rp=0;
    while(x){
        rp+=(x/y),x/=y;
    }
    return rp;
}
inline void print1(__int128 x,__int128 y){
    __int128 ans=1e17;
    for(__int128 i=2;i<=y;++i){
        __int128 p=0;bool flag=0;
        while(y%i==0){
            y/=i;++p;flag=1;
        }
        if(flag){
            ans=min(ans,calc(x,i)/p);
        }
    }
    write(ans);
    return;
}
inline void print2(__int128 x){
    write(res[x]);
}
signed main(){
    __int128 x=read(),y=read();
    __int128 z=(x%min(13,y)+1);
    f[1]=f[2]=1;
    if(x==1){
        print1(x,y);
        return 0;
    }
    for(__int128 i=3;i<=500;++i){
        if(x-f[i-1]==f[i-2]){
            print1(x,y);
            return 0;
        }
        if(x-f[i-1]<f[i-2]){
            print2(z);
            return 0;
        }
        f[i]=(f[i-1]+f[i-2]);
    }
    return 0;
}