Stuck in optimizing this question from past few days

linke to the question:
https://www.chegg.com/homework-help/questions-and-answers/5-paint-ceiling-want-build-house-building-company-hired-build-houses-sides-specific-set-s--q43901799

was asked in an online test by company, couldn't solve it due to time limit , been stuck in my mind for last few days plzz help.

//test case values were very large as even the count variable needed to be of long type so that's why i took variable long.
//timelimit is 4ms.

my solution:

import java.util.*;
public class Main
{
public 
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int s=sc.nextInt();
int k=sc.nextInt();
int b=sc.nextInt();
int m=sc.nextInt();
long a=sc.nextLong();
long res[]=new long[n];
res[0]=s;
long prev=s;
for(int i=1;i<n;i++)
{
res[i]=((k*prev+b)%m)+1+prev;
prev=res[i];
}
long c=0;
int f=0;
int max=res.length;
for(int i=0;i<max;i++)
{
for(int j=i;j<max;j++)
{
long prod=res[i]*res[j];
if(prod<=a)
{
c++;
if(i!=j)
c++;
}
else{
if(i==j)
{
f=1;
break;
}
max=j;
break;
}
}
if(f==1)
break;
}
System.out.print(c);
return ;
}
}```
</details>
# 答案1
**得分**: 1
如果你提交了这份完全相同的代码，接下来听到的是“谢谢但不用了”，请考虑一下代码风格可能相当糟糕（变量名过于简短，数组括号在名称后面，这在任何风格指南中都是错误，混合使用制表符和空格等等）。
但总的来说，这有点奇怪：这些类型的编码练习通常在学术上要求你为了时间效率而做出风格上奇怪的事情。整个重点几乎是创建“只写”代码：它不需要维护，问题描述永远不会改变。我会说，任何将对这类练习编写的代码评估风格的公司都很愚蠢，但这种情况已经出现过——你问题中的一条评论就犯了同样的错误，认为风格在这些练习中很重要。
## 为什么你的算法太慢
问题在于，你的算法是O(N<sup>2</sup>)。但可以用O(N log N)的复杂度解决——而你的优化根本不起作用。虽然你的优化很聪明，但实际上并没有减少复杂性。
这里有一个针对这类问题的提示：思考“元”。你本可以知道，你的优化策略对于具体的问题毫无用处（特别是，一旦你达到超过a的组合，你就将max降低）：
问题描述会让我定义一个数据集，使得你拥有，比如，n = 6*10<sup>7</sup>（即600万个侧面），而a非常大，足以使得__每个侧面组合__都会成功。
在这种情况下，你算法的优化根本不会生效，因此你会运行600万*600万次操作，远远超过100亿次，而这基本上是操作开始变得明显耗时的魔法数字。
这些问题几乎总是会给你提供最坏情况的场景。所以，它们会将这种“许多侧面的每个组合都适合于a”的情况输入到你的算法中，因此它会因为超时而失败。
换句话说，你所添加的任何对最坏情况没有影响的优化都是__无用的__——这些问题的设计和编写是为了正确的优化在__每个相关情况__下都有效。因此，你本可以知道，你聪明地想到的“max=j”技巧实际上并不是关键答案。
## 那么，正确的答案是什么呢？
内部循环是不必要的。
假设你的侧面输入集是[2,3,4,5,20,100,101]。
然后循环遍历每个侧面。
对于给定的侧面：首先计算其他侧面可能有多大。那简单地是`a/2`，`a/3`等等。接下来，使用二分搜索找到小于或等于该数字的最高索引（二分搜索是O(logn)）。然后确定该侧面的数字是否在该数据集中（2在其中吗？）。如果没有，在答案中加上（索引*2）。如果是，从中减去1（因为2/2只有一种配置，而2/4表示两种配置：2/4和4/2）。
就是这样。这在每次操作中执行一个O(1)+O(nlogn)的操作，总复杂度为O(nlogn)。
O(nlogn)轻松处理“n=百万”的情况。
<details>
<summary>英文:</summary>
If you handed in this exact code and the next thing you heard is &#39;thanks but no thanks&#39;, consider that the style is pretty bad (extremely short variable names, the array brackets after the name which is a faux pas in _every_ style guide out there, mixing tabs and spaces, yadayada.
But as a rule, that&#39;s a little weird: These kinds of coding exercises are all highly academic and usually require you to do otherwise stylistically weird things for time expediency. The whole point is pretty much to create &#39;write only&#39; code: It does not need to be maintained and the problem description never changes. I would say any company that rates code written for such exercises on style is being very very silly, but it&#39;s been known to happen - and one of the comments on your question is, for example, making the same error and thinking that style is somehow important for these exercises.
## Why your algorithm is too slow
The problem is, your algorithm is O(N&lt;sup&gt;2&lt;/sup&gt;). But it can be done in O(N log N) - and your optimization simply does not count. It&#39;s a clever optimization but it doesn&#39;t actually reduce the complexity at all.
Here&#39;s a tip for these kinds of problems: Think &#39;meta&#39;. You could have known that your optimization strategy is useless for the specific problem at hand (specifically, your optimization of turning `max` down once you hit a combo that exceeds `a`):
The problem description would let me define a dataset such that you have, say, n = 6*10&lt;sup&gt;7&lt;/sup&gt; (so, 6 million sides), and `a` so large that __every combination of siding__ will succeed.
In that case, your algorithm&#39;s optimizations simply do not ever kick in, and thus you&#39;d run 6million*6million operations, that&#39;s well over 10 billion, and that&#39;s more or less the magic number where operations start taking noticable time.
These problems tend to almost always give you that worst case scenario. So, they WILL feed this &#39;every combination of the many many sidings all fit within `a`&#39; scenario to your algorithm, and thus it will fail due to timeout.
In other words, any optimization you care to add that does nothing to the worst case scenario you can think of __is useless__ - these problems are designed and written so that the right optimization works for __every relevant case__. Thus, you could have known that `max=j` trick you cleverly thought of, isn&#39;t actually the key answer.
## Okay, so what is the right answer then?
The inner loop is not neccessary.
Let&#39;s say your input set of sidings is [2,3,4,5,20,100,101].
Then loop through each siding.
For a given siding: First calculate how large the other siding could possibly be. That&#39;s simply `a/2`, `a/3`, etcetera. Next, use binary search to find the highest index whose number is less than or equal to that number (binary search is O(logn)). Then figure out if this siding&#39;s number is in that data set (is 2 in there?). If no, add (index*2) to the answer. if yes, subtract 1 from that (because 2/2 is only one config, whereas 2/4 represents 2 configs: 2/4 and 4/2).
And that&#39;s it. It&#39;s doing an O(1)+O(nlogn) operation n times, for a total complexity of O(nlogn).
O(nlogn) can trivially handle &#39;n=millions&#39;.
</details>