四川大学第二届SCUACM新生赛——J. n=abc

淩亂°似流年 2023-06-14 05:30 27阅读 0赞

给你一个整数 n(1<=n<=100000), 请你将其拆成三个整数 a,b,c (1<a<=b<=c<n), 的乘积，要求 c-a 尽可能小，在此前提下，a 也尽可能小。

输入描述:  
第一行一个整数 T(1<=T<=1000) 表示数据组数。  
对于每组数据，一个整数 n(1<=n<=100000) 。

输出描述:  
如果可以拆成三个整数的乘积，输出一行形如 n=a \* b \* c 的信息，其中 a,b,c 按升序排列。  
如果不能拆成三个整数的乘积，输出 No solution 。

示例1

输入

2  
12  
10

输出

12=2 \* 2 \* 3  
No solution

题解：分别暴力枚举a,b,c，c-a的最小值跑一遍就得出，  
a,b,c最后的顺序一定是升序（ i \* i \* i 和 j \* j 可以判断）。

#include<iostream>
    using namespace std;
    typedef long long ll; 
    int main()
    { 
    	int t;
    	cin>>t;
    	while(t--)
    	{ 
    		int n,a,b,c,ans=100000;
    		cin>>n;
    		for(ll i=2;i*i*i<=n;i++)//a
    		{ 
    			if(n%i==0)
    			{ 
    				int x=n/i;//b*c
    				for(ll j=i;j*j<=x;j++)//b
    				{ 
    					if(x%j==0&&x/j-i<ans)
    					{ 
    						ans=x/j-i;//c-a的最小值 
    						a=i;
    						b=j;
    						c=x/j;
    					}
    				}
    			}
    				
    		} 
    		if(ans==100000)
    			cout<<"No solution"<<endl;
    		else
    			cout<<n<<"="<<a<<"*"<<b<<"*"<<c<<endl;
    	}
    	
    	return 0;
     }

发表评论取消回复

表情：

评论列表（有 0 条评论，27人围观）

还没有评论，来说两句吧...

相关阅读

相关 2019燕山大学程序设计新生赛（二）

2019燕山大学程序设计新生赛（二）绝地武士参考代码织梦岛参考代码

你的名字/ 2023年06月22日 05:24/ 0 赞/ 93 阅读

相关 2019燕山大学程序设计新生赛（一）

2019燕山大学程序设计新生赛（一）伯劳的问题参考代码宝可梦大师参

- 日理万妓/ 2023年06月22日 05:19/ 0 赞/ 91 阅读

相关四川大学第二届SCUACM新生赛——J. n=abc

给你一个整数 n(1<=n<=100000), 请你将其拆成三个整数 a,b,c (1<a<=b<=c<n), 的乘积，要求 c-a 尽可能小，在此前提下，a 也尽可能小。

淩亂°似流年/ 2023年06月14日 05:30/ 0 赞/ 28 阅读

相关四川大学图书馆数据库

http://202.115.54.17:8088/V/M9T1RVGI92I8EJUAPSKBHFNUQMKPT4MC3IQ4L464S5ICNNTREX-02694?FUN

╰+哭是因爲堅強的太久メ/ 2022年08月09日 05:25/ 0 赞/ 257 阅读

相关 2018NYIST新生第二次周赛参考题解

比赛网址：[http://nyoj.top/web/contest/show/cid/68][http_nyoj.top_web_contest_show_cid_68] 密

傷城~/ 2022年05月11日 13:44/ 0 赞/ 234 阅读

相关长沙理工大学ACMore编程协会2018年新生赛（重现赛）

A 送气球.jpg 链接：https://ac.nowcoder.com/acm/contest/318/A 来源：牛客网题目描述 ACM-ICPC程序设计大赛

古城微笑少年丶/ 2022年04月03日 19:51/ 0 赞/ 352 阅读

相关山东财经大学新生赛暨天梯赛选拔赛 D 流星雨 (区间贪心)

链接：[https://ac.nowcoder.com/acm/contest/547/D][https_ac.nowcoder.com_acm_contest_547_D]

绝地灬酷狼/ 2022年03月07日 09:20/ 0 赞/ 285 阅读

相关山东财经大学新生赛暨天梯赛选拔赛 C Retina

链接：[https://ac.nowcoder.com/acm/contest/547/C][https_ac.nowcoder.com_acm_contest_547_C]

约定不等于承诺〃/ 2022年03月07日 08:46/ 0 赞/ 315 阅读

相关山东财经大学新生赛暨天梯赛选拔赛 A 骆驼拼写法

链接：[https://ac.nowcoder.com/acm/contest/547/A][https_ac.nowcoder.com_acm_contest_547_A]

浅浅的花香味﹌/ 2022年03月07日 08:44/ 0 赞/ 280 阅读

相关长春理工大学第十四届程序设计竞赛（重现赛）J

J.Printout 题目：链接：[https://ac.nowcoder.com/acm/contest/912/J][https_ac.nowcoder.com_a

淩亂°似流年/ 2022年01月07日 15:35/ 0 赞/ 339 阅读