题解：P14789 [NERC 2025] Honey Cake

· · 题解

题意：给出一个长为 w 宽为 h 高为 d 的长方体蛋糕，求是否存在一种情况可以正好切成 n 块相等的蛋糕分给 n 个人。

很容易想到找出所有 n 的因子并存储，枚举求是否可行。

使用双层循环保证枚举到每一种情况，对于每一对因子，用 n 再算一个商，判断三个数是否分别正好能被长，宽，高整除，也就是切成的小蛋糕相同，如果有就输出结束程序，没有输出负一即可。

一个坑：注意输出是要减一，因为把线段分成 n 段要切割 n 减一次。

代码：

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll w,h,d,n;//题目数据 
vector <ll> a;//用于存储n的因子，因为数量不确定，用vector 
void init(ll n){//处理因子 
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            a.push_back(i);//是倍数先进入 
            if(i*i!=n){//不是平方数是还要进入另一个对应的 
                a.push_back(n/i);//进入另一个因子 
            }
        }
    }
    return ;
}
signed main(){
    scanf("%lld%lld%lld%lld",&w,&h,&d,&n);//读入 
    init(n);//找因子 
    ll len=a.size();
    for(ll i=0;i<len;i++){//双层循环保证枚举每一种情况 
        for(ll j=0;j<len;j++){
            if(n%(a[i]*a[j])!=0){
                continue;//如果n不是倍数直接跳过 
            }
            ll k=n/(a[i]*a[j]);//求商 
            if(w%a[i]==0&&h%a[j]==0&&d%k==0){//判断三个是不是都符合条件 
                ll cnt1=a[i]-1;//注意输出是时要减一 
                ll cnt2=a[j]-1;//同上 
                ll cnt3=k-1;//同上 
                printf("%lld %lld %lld\n",cnt1,cnt2,cnt3);//输出 
                return 0;//直接结束程序，因为找到一种就行 
            }
        }
    }
    printf("-1");//运行到这里说明没有答案，输出-1 
    return 0;//结束程序 
}