牛客算法周周练2

链接：https://ac.nowcoder.com/acm/contest/5203/E
来源：牛客网

时间限制：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

输出

说明

打个表我们发现f(i)其实就是个斐波那契数列, 然后我们只需要先判断x是不是斐波那契数

1、如果是的话输出x阶乘在m进制下末尾0的个数

x阶乘在m进制下末尾0的个数，就是x的阶乘可以分解出多少个m

举个例m=60，60=2*2*3*5

所以我们看x的阶乘可以分解出多少对(2, 2, 3, 5)

我们可以分别求出x的阶乘中可以分解出的2的个数a、3的个数b、5的个数c

int cal_p(int n, int p)//计算n!中有多少质因子p 
{
    int res=0;
    while(n)
    {
        res+=n/p; 
        n/=p;
    }
    return res;
}

ans = min(a/2, b/1, c/1)，后面除的数就是m分解出的每个质因数的个数，比如m=60，每两个2才能凑出一个(2, 2, 3, 5)对

2、不是的话就是个n皇后问题

求z皇后方案数，z的生成是：z=x%min(13,m)+1，所以z的范围为1-13，我们DFS求，但是z只有13个，没必要浪费时间DFS，直接打表就完事了（如何打表在最下面）

 1 #include <bits/stdc++.h>
 2 typedef long long LL;
 3 #define pb push_back
 4 const int INF = 0x3f3f3f3f;
 5 const double eps = 1e-8;
 6 const int mod = 1e9+7;
 7 const int maxn = 1e5+10;
 8 using namespace std;
 9 
10 int queen[]={0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712};//皇后问题的解
11 LL fib[5005];//斐波那契数列
12 int cnt;//斐波那契数列项数
13 
14 int main()
15 {
16     #ifdef DEBUG
17     freopen("sample.txt","r",stdin); //freopen("data.out", "w", stdout);
18     #endif
19     
20     fib[1]=fib[2]=1;//斐波那契打表
21     for(cnt=3;fib[cnt-1]<=1e18;cnt++)
22         fib[cnt]=fib[cnt-1]+fib[cnt-2];
23     LL n, m;
24     scanf("%lld %lld",&n,&m);
25     int flag = 0;
26     for(int i=1;i<=cnt;i++)//查找n是否是斐波那契数列
27     {
28         if(fib[i]==n)
29         {
30             flag=1;
31             break;
32         }
33     }
34     if(flag)//是的话输出阶乘在m进制下末尾0的个数
35     {
36         vector<pair<int,int> > fac;
37         for(int i=2;i*i<=m;i++)//先对m分解质因数
38         {
39             if(m%i==0)
40             {
41                 int cnt=0;
42                 while(m%i==0)
43                 {
44                     m/=i;
45                     cnt++;
46                 }
47                 fac.pb({i,cnt});
48             }
49         }
50         if(m > 1) fac.pb({m,1});
51         LL ans = 4e18;
52         for(int i=0;i<fac.size();i++)
53         {
54             LL t = n;
55             LL res = 0;
56             while(t)
57             {
58                 res += t/fac[i].first;
59                 t /= fac[i].first;
60             }
61             ans=min(ans, res/fac[i].second);
62         }
63         printf("%lld
", ans);
64     }
65     else printf("%d
",queen[n%min(13LL,m)+1]);//不是的话输出Z皇后的解
66     
67     return 0;
68 }

附Z皇后打表：

 1 #include <bits/stdc++.h>
 2 typedef long long LL;
 3 #define pb push_back
 4 const int INF = 0x3f3f3f3f;
 5 const double eps = 1e-8;
 6 const int mod = 1e9+7;
 7 const int maxn = 1e5+10;
 8 using namespace std;
 9 
10 int jm[3][55];
11 int ans;
12 
13 void DFS(int num, int k)
14 {
15     if(num>k)
16     {
17         ans++;
18         return;
19     }
20     for(int i=1;i<=k;i++)
21     {
22         if(jm[0][i]==0&&jm[1][num-i+k]==0&&jm[2][num+i]==0)
23         {
24             jm[0][i]=jm[1][num-i+k]=jm[2][num+i]=1;
25             DFS(num+1,k);
26             jm[0][i]=jm[1][num-i+k]=jm[2][num+i]=0;
27         }
28     }
29 }
30 
31 int main()
32 {
33     #ifdef DEBUG
34     freopen("sample.txt","r",stdin); //freopen("data.out", "w", stdout);
35     #endif
36     
37     for(int k=1;k<=13;k++)
38     {
39         ans=0;
40         DFS(1,k);
41         printf("%d ",ans);
42     }
43     
44     return 0;
45 }