发布时间：2023-09-04

CF633题解

B - A Trivial Problem（数论+二分查找）

题意：给定一个整数m,找出整数N使N！有m个后导0
思路：将 $N!$ 分解因数必定得到 $10^m$ ，而10可以拆成2*5，m即为质因数中2和5的指数最小值
易知2的指数必定比5的指数大
因此题目化简为有几个N使N！的阶层5的指数为m
可以二分查找，复杂度 $O(log(1e9))$

void solve(){
	int n;
	cin>>n;
	ll l=1,r=1e9;
	auto check=[&](int x){
		ll ans=0;
		while(x){
			ans+=x/5;
			x/=5;
		}
		return ans;
	};
	while(l<r){
		ll mid=l+r>>1;
		if(check(mid)>=n)r=mid;
		else l=mid+1;
	}
	if(check(l)==n){
		cout<<"5\n";
		for(int i=l;i<=l+4;i++)cout<<i<<" ";
		cout<<"\n";
	}
	else cout<<"0\n";
}

D - Fibonacci-ish(暴力+map)

题意：给定一个数组a，求能组成的最长斐波那契数列 思路：斐波那契数列只取决于第一个数和第二个数，用map存出现过的数的次数，枚举前两个数，然后dfs
最坏复杂度：$O(N^3)$
特别记录0的个数，前两个数为0时直接更新为0的个数，防止复杂度退化为 $N^3$

ll a[1010];
map<ll,ll> vis;
ll ans=0;
//bool solve(){
void dfs(ll x,ll y,ll len){
	ans=max(ans,len);
	if(vis[x+y]){
		vis[x+y]--;
		dfs(y,x+y,len+1);
		vis[x+y]++;
	}
}
void solve(){
	int n;
	cin>>n;
	ll cnt=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		vis[a[i]]++;
		if(a[i]==0)cnt++;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			if(a[i]==0&&a[j]==0){
				ans=max(ans,cnt);
				continue;
			}
			vis[a[i]]--;
			vis[a[j]]--;
			dfs(a[i],a[j],2);
			vis[a[i]]++;
			vis[a[j]]++;
		}
	}
	cout<<ans<<"\n";
}
signed  main() {
	cin.tie(0)->sync_with_stdio(0);
    //init();
	int T=1;
	//cin >> T;
	//while(T--)cout<<(solve()?"YES\n":"NO\n");
   	while (T--)solve();
   	return 0;
}