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

WydnksqhbD · 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 条鱼。逐次倒推得： 10\times\frac{3}{2}+1=16 16\times\frac{3}{2}+1=25

  故最终的答案为 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;
}