行业网站建设收费明细,外贸业务员怎么开发客户,百度不做网站外链是什么原因,网站设计风格大全题目 分析
上来一看#xff0c;三个for循环#xff0c;从1到n#xff0c;寻找满足lwhn的个数#xff0c;但是这样根本跑不出来答案#xff0c;n太大了#xff0c;1e15的级别#xff0c;O#xff08;n#xff09;的时间复杂度都不行#xff0c;更何况是O#xff08;…题目 分析
上来一看三个for循环从1到n寻找满足lwhn的个数但是这样根本跑不出来答案n太大了1e15的级别On的时间复杂度都不行更何况是On^3。 尝试降低时间复杂度很难可以尝试降低数据规模。 插入理论影响代码运行时间的两个因素算法时间复杂度和数据规模。 我们可以观察一下满足lwhn的lw和h有什么特点。他们肯定是n的因子那么我们只需要遍历n的因子就可以了。怎么求n的因子呢一个for循环遍历即可时间复杂度是Osqrtn满足要求。
解题
第一步 求n的因子的代码如下
long n 2021041820210418l;SetLong set new HashSetLong();for(long i 1;i n / i;i) {if(n%i0) {set.add(i);set.add((n/i));}}因为找到一个小于sqrt(n)的因子i必然也能根据i找到大于sqrt(n)的另一个因子即n/i。 第二步 遍历n的因子
long ans 0;for(Long a:set)for(Long b:set)for(Long c:set)if(a*b*cn) ans;第三步 输出答案
System.out.println(ans); 完整代码
import java.util.HashSet;
import java.util.Set;public class 货物摆放 {
public static void main(String[] args) {long n 2021041820210418l;//2430SetLong set new HashSetLong();for(long i 1;i n / i;i) {if(n%i0) {set.add(i);set.add((n/i));}}long ans 0;for(Long a:set)for(Long b:set)for(Long c:set)if(a*b*cn) ans;System.out.println(ans);
}
}
