温州网站建设得花多少钱,上海网站建设自学,做门户型网站,怎么做网页内容公证传送 时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K 64bit IO Format: %lld 题目描述 其中#xff0c;f(1)1;f(2)1;Z皇后的方案数#xff1a;即在ZZ的棋盘上放置Z个皇后#xff0c;使其互不攻击的方案数。…传送 时间限制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%m0)
{tot;W/m;
}//tot计数可以得到 Wa * mtotn是mtot的倍数
末尾几个0tot就是几tot是记录末尾0 的数量
我们看 n ! 最多可以分解出多少个m 质因数 pi 设mp1a1 *p2a2 *…*pkak W n! n a * m tot na * p1a1 *p2a2 *…*pkaktot
n!a * p1b1 *p2b2 *…*pkbk
bkak *tot
求出x最多可以分解出多少个pi
totmin(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 sum0;while(n){sumn/m;n/m;}return sum;
}//n!的质因子p的个数void ans_solve(){ll ans1e183;Mm;for (int i 1; prime[i] M; i) {while (M % prime[i] 0) {ans1[prime[i]];M / prime[i];}}for(int i1;i25;i){if(ans1[prime[i]]){ans2[prime[i]]getsum(x,prime[i]);}}for(int i1;i25;i){if(ans1[prime[i]])ansmin(ans,ans2[prime[i]]/ans1[prime[i]]);}coutansendl;
}3.求z皇后方案数 zx%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];
