水题(water)_牛客博客

传送

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述
在这里插入图片描述

其中，f(1)=1;f(2)=1;Z皇后的方案数：即在Z×Z的棋盘上放置Z个皇后，使其互不攻击的方案数。

输入描述:

输入数据共一行，两个正整数x,m，意义如“题目描述”。

输出描述:

一个正整数k，表示输出结尾0 的个数或者放置皇后的方案数

示例1
输入

375 16

输出

说明
在这里插入图片描述
题解：
看了一阵子没明白，也是从其他人那学完之后，自己总结着再写
这个题内含三个小题：
1.判断是否存在k使得f(k)=xf(k)=x
2.n!在m进制下末尾零的个数
3.Z皇后方案数
解答：（非详细）
1.F函数其实就是斐波那契数列

斐波那契数列平方和的性质：（就是题目中所给公式）
在这里插入图片描述

    fi[1] = 1, fi[2] = 1;
    for (int i = 3;; ++i) {
        fi[i] = fi[i - 1] + fi[i - 2];
        if (fi[i] > 1e18) break;
    }

2.求n!在m进制的末尾0个数

首先一个结论：n!的质因子p的个数等于：1~n中p的倍数(n/p)加上(n/p)!中质因子p的个数

然后：
写出
将数W转化成m进制的末尾0的个数
的暴力代码是：

while(W%m==0)
{
    tot++;
    W/m;
}//tot计数

可以得到 W=a * m^tot^（n是m^tot^的倍数）

末尾几个0，tot就是几（tot是记录末尾0
的数量）

我们看 n ! 最多可以分解出多少个m
质因数 pi
设m=p1^a1^ p2^a2^ *....pk^ak^
W = n!
n！= a * m ^tot^
n！=a * （p1^a1^ p2^a2^ *....pk^ak^）^tot^

n!=a * p1^b1^ p2^b2^ *....pk^bk^

bk=ak *tot

求出！x最多可以分解出多少个pi

tot=min(bk/ak)
枚举k

ll prime[maxn] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};

ll getsum(ll n,ll m){
    ll sum=0;
    while(n)
    {
        sum+=n/m;
        n/=m;
    }
    return sum;
}//n!的质因子p的个数

void ans_solve(){
    ll ans=1e18+3;
    M=m;
    for (int i = 1; prime[i] <= M; ++i) {
        while (M % prime[i] == 0) 
        {
            ++ans1[prime[i]];
            M /= prime[i];
        }
    }

    for(int i=1;i<=25;i++){
        if(ans1[prime[i]])
        {
            ans2[prime[i]]=getsum(x,prime[i]);
        }
    }

    for(int i=1;i<=25;i++){
        if(ans1[prime[i]])
        ans=min(ans,ans2[prime[i]]/ans1[prime[i]]);
    }
    cout<<ans<<endl;
}

3.求z皇后方案数
z=x%min(13,m)+1
根据式子就能得到z的范围在1~13，范围不大直接打表就可以

ll dabiao()
{
      z[1]=1;z[2]=0;z[3]=0;z[4]=2;
      z[5]=10;z[6]=4;z[7]=40;z[8]=92;
      z[9]=352;z[10]=724;z[11]=2680;
      z[12]=14200;z[13]=73712;

 } 
cout<< z[x%min(13*1ll,k)+1];