时间限制：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 * mtot（n是mtot的倍数）
末尾几个0，tot就是几（tot是记录末尾0
的数量）
我们看 n ! 最多可以分解出多少个m
质因数 pi
设m=p1a1 *p2a2 *…*pkak
W = n!
n！= a * m tot
n！=a * （p1a1 *p2a2 *…*pkak）tot
n!=a * p1b1 *p2b2 *…*pkbk
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];
京公网安备 11010502036488号