自动搬运

查看原文

来自洛谷，原作者为

	WydnksqhbD **

搬运于2025-08-24 21:15:57，当前版本为作者最后更新于2024-01-31 21:04:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

B3925 [GESP202312 三级] 小猫分鱼 题解

本题提供两种思路。

思路 1

枚举第 $N$ 只小猫拿走的鱼数，每次往回倒推即可。

例如：$N=3,i=1$ 时，

• 若拿了 $1$ 条，则在第 $3$ 只小猫分之前，有 $1\times3+1=4$ 条鱼。$4$ 可以被 $2$ 整除。在第 $2$ 只小猫分之前，有 $4\times\frac{3}{2}+1=7$ 条鱼。此时不能被 $2$ 整除，故舍去。
• 若拿了 $2$ 条，则在第 $3$ 只小猫分之前，有 $2\times3+1=7$ 条鱼。不符题意，故舍去。
• 若拿了 $3$ 条，在第 $3$ 只小猫分之前，有 $3\times3+1=10$ 条鱼。逐次倒推得：

故最终的答案为 $25$ 条。

（代码最后给）

思路 2

枚举答案。

这样仅需递推即可。但是时间复杂度较高，现在本蒟蒻仅想出了改变起点的方式优化。如果你有更好的优化，可以私信我。

代码

思路 1 C 风格代码

#include<stdio.h>
int main()
{
	long long n,i,j,k;
	scanf("%lld %lld",&n,&i);
	for(j=1;;j++)
	{
		int flag=1;
		long long ans=j*n+i;
		for(k=1;k<n;k++)
		{
			if(ans%(n-1)){flag=0;break;}
			ans=ans/(n-1)*n+i;
		}
		if(flag)
		{
			printf("%lld",ans);
			return 0;
		}
	}
}

思路 1 C++ 风格代码

#include<iostream>
using namespace std;
int main()
{
	long long n,i,j,k;
	cin>>n>>i;
	for(j=1;;j++)
	{
		bool flag=true;
		long long ans=j*n+i;
		for(k=1;k<n;k++)
		{
			if(ans%(n-1)){flag=false;break;}
			ans=ans/(n-1)*n+i;
		}
		if(flag)
		{
			cout<<ans;
			return 0;
		}
	}
}

思路 2

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans;
bool check(int x)
{
	for(int i=1;i<=n;i++)
	{
		x-=m;
		if(x<=0||x%n)return false;
		x=x/n*(n-1);
	}
	return true;
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(ans=(n>8)?380000000:1;;ans++)
	{
		if(check(ans))break;
	}
	printf("%lld",ans);
	return 0;
}