1744 被盗的食物

 羊村的羊们为了过冬,他们要在夏天的时候存储一些食物。等到冬天时拿出来吃。他们把食物包装成1×1×1的小方块,以便存储和取出来食用。经过了一个夏天后,小羊们存储了A·B·C块食物。他们把食物放到一个长方体的小屋里,A层高,每层有B行,每行有C块食物。

    在秋天过后,村长来到小屋,要打开门分发食物了。但是,很不幸,小屋的四周都散落着食物块。经过查证,小偷们从小屋的顶层,前面,后面,和侧面都偷走了一个面的食物,一个面的食物指的是紧贴着某个面食物。所以剩下只有 (A−1)×(B−2)×(C−2)(A−1)×(B−2)×(C−2) 块食物。为了隐藏罪证,小偷们把剩下的食物块,全部打乱,散落在小屋的四周。所以村长忘记了原来A,B,C到底是多少。

 现在给定n,表示剩下的食物数量。计算可能最小和最大被偷走的食物数量。

样例解释:

在样例中,如果原来的数量为 $32=2×4×4$,现在的数量是 $4=(2-1)×(4-2)×(4-2)$,则被偷走的是32-4=28块。 如果原来的数量为45=5×3×3,现在的数量是$4=(5-1)×(3-2)×(3-2)$,则被偷走的是45-4=41块。

 收起

输入 单组测试数据。 第一行一个整数n $(1≤n≤10^9)$代表剩下的食物块。 输出 共一行,两个整数用空格隔开,第一个表示最小可能被偷的食物的数量,第二个表示最多可能被偷的食物的数量。 输入样例 4 输出样例 28 41 解题思路 :  暴力是三层for循环   铁定T ,优化成  。优化的话是一个数学问题 , 我大致写一下,

图片名称

#include <iostream>
#include <cstdio>
#include <algorithm> 
using namespace std ;
typedef long long LL;  
const LL inf = 0x3f3f3f3f3f3f3f3f; 
LL minn = inf ; 
LL maxx = -inf ;
LL n ;   
int main() {

	cin >> n ; 

	for(LL i = 1 ; i*i*i<=n; i++) {
		
		if( n% i !=0) continue ; 
		LL t1 = n/i ; 
		for(LL j = i ; j*j<=t1 ; j++ ) {
			if(t1 %j !=0) continue ; 
			LL t2 = t1/ j ; 
			
			LL k = t2 ; 
			minn = min(minn,(i+1)*(j+2)*(k+2)) ;
			maxx = max(maxx,(i+2)*(j+2)*(k+1)) ; 
			
		}
		
	}
	minn -=n ; 
	maxx -=n ; 
	cout<<minn <<" " <<maxx<<endl;  
	return 0 ; 
}


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×