C++ 解法, 执行用时: 3ms, 内存消耗: 440K, 提交时间: 2023-08-12 11:20:17

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll x,p,q,ans,ge,add;
int m;
map<ll,int> F;
int G[14]={0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712};

int main(){
	cin>>x>>m;
	p=q=1;F[1]=1;
	for(int i=1;;i++){
		ll t=p;
		p+=q,q=t;
		if(p>1e18) break;
		F[p]=1;
	}
	if(F[x]){
		ans=1e18;
		for(int i=2;i<=m;i++){
			if(m%i==0){
				ge=0;while(m%i==0) ge++,m/=i;
				ll tmp=x;add=0;
                while(tmp) add+=tmp/i,tmp/=i;
                ans=min(ans,add/ge);
			}
		}
	}
	else x=x%min(13,m)+1,ans=G[x];
	cout<<ans;

	return 0;
}