链接 ： 传送们
这个式子是斐波那契数列的一个，更多见 斐波那契数列常见式子
那这道题就简单了，就是x 是否为斐波那契数列
1. 是 输出 x! 在m进制下的末尾0的个数
2. 不是 输出 z (1-13) 皇后问题的个数
一 求末尾0的个数
10进制下如何求 ？ 那就是求 2和5的个数 why？ 2*5=10 正好为10 ，其他进制也一样，只需找到所有相乘为m的数的个数，但x太大，肯定没办法直接暴力求，于是想办法简化 ， 任何数都能由质数的乘积构成 而我们求的就是乘积等于m的数的个数 于是就变成了求质数的个数 ，把m分解为质数，然后求x!中有多少个
二 求n皇后问题
先上代码
int uplimit;
void dfs(int row,int ld,int rd){if(row!=uplimit){int pos=uplimit& (~(row|ld|rd)); //取反 求能放的位置while(pos){ //循环求所有放的可能int p=pos&-pos; // 等价于 pos&(~pos+1) 末尾1 从末尾一个一个尝试放pos-=p; dfs(p|row,((ld | p)<<1),(rd | p)>>1); //p|row 放的位置为p p|row 就是放好的 (ld | p) << 1 左斜线 (rd | p) 右斜线线}}else ans++;}uplimit 就是放完 也就是 (1 < < n ) -1 变成二进制是n个 1
ld 左边 rd 右边
初始化
uplimit =(1<<n)-1
dfs(0,0,0) 初始未放 所以都为 0
代码 :
#include <bits/stdc++.h>
using namespace std;
long long fib[100];
long long maxx=1;
long long prime[] = {
0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
long long ans=0;
int uplimit;
void dfs(int row,int ld,int rd){if(row!=uplimit){int pos=uplimit& (~(row|ld|rd));while(pos){int p=pos&-pos; // 等价于 pos&(~pos+1) pos-=p;dfs(p|row,((ld | p)<<1),(rd | p)>>1);}}else ans++;}
int num[66];
int wei=0;
int ling[20];
int cnt[40];
void solve(long long x,long long m){for(int i=1;i<=25;i++){while(m%prime[i]==0){cnt[i]++;m/=prime[i];}}long long ans=1e18;long long temp;for(int i=1;i<=25;i++){if(cnt[i]){long long k=0;temp=x;while(temp){temp/=prime[i];k+=temp;}ans=min(ans,k/cnt[i]);// cout<<prime[i]<<" "<<x<<" "<<k<<endl;}}cout<<ans<<endl;}
void init(){fib[0]=1;fib[1]=1;fib[2]=2;maxx=3;while(fib[maxx-1]<=1e18){fib[maxx]=fib[maxx-1]+fib[maxx-2];maxx++;}for(int i=1;i<=13;i++){uplimit= (1<<i)-1;ans=0;dfs(0,0,0);ling[i]=ans;}}
int main()
{init();long long a;int m;cin>>a>>m;if(fib[lower_bound(fib,fib+maxx,a)-fib]==a){solve(a,m);}else{int z=(a% min(13,m))+1;cout<<ling[z] ;}return 0;
}