水题(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

输出

14200

说明

题解：
看了一阵子没明白，也是从其他人那学完之后，自己总结着再写
这个题内含三个小题：
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=p₁^a1 *p₂^a2 *…*p_k^ak
W = n!
n！= a * m ^tot
n！=a * （p₁^a1 *p₂^a2 *…*p_k^ak）^tot

n!=a * p₁^b1 *p₂^b2 *…*p_k^bk

b_k=a_k *tot

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

tot=min(b_k/a_k)
枚举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];