Java中的大型优化IO处理
订单10^18的输入n和输出应该是其设定位仅为2的所有数字的总和。对于例如n = 5个setbit是101-> 2个设定位。对于n = 1234567865432784,我如何优化下面的代码?Java中的大型优化IO处理
class TestClass
{
public static void main(String args[])
{
long N,s=0L;
Scanner sc = new Scanner(System.in);
N=sc.nextLong();
for(long j = 1; j<=N; j++)
{
long b = j;
int count = 0;
while(b!=0)
{
b = b & (b-1);
count++;
}
if(count == 2)
{
s+=j;
count = 0;
}
else
{
count = 0;
continue;
}
}
System.out.println(s%1000000007);
s=0L;
}
}
Java提供的类BigInteger
,这包括一种方法nextProbablePrime()
。这意味着你可以做这样的事情:
BigInteger n = new BigInteger(stringInputN);
BigInteger test = BigInteger.valueOf(2);
BigInteger total = BigInteger.valueOf(0);
while (test.compareTo(n) < 0){
total = total.add(test);
test = test.nextProbablePrime();
}
System.out.println(total);
这这有得到错误的答案(但非零)的概率极低,所以你可能要运行它两次,只是双检。它应该比手动迭代手动更快。
Java有一个功能
if (Integer.bitCount(i) == 2) { ...
但是考虑了一下:这是数字检查的很多。
怎么样生成所有只有两位数的数字?
设置我个和j 个位的n
:
int n = (1 << i) | (1 << j); // i != j
现在考虑31²步骤,尚未1000 N步。
因为这是我的功课提醒:
尝试扭转这个问题,做了最少的功,后退一步,找到聪明的做法,搜索数学核心。 并享受。
下一次,不要破坏自己的成功时刻。
正如你可能有足够的时间去思考乔普埃根的建议, 这里是如何我会做(这是乔普描述我认为):
import java.util.Scanner;
public class Program {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
long sum = 0;
for (int firstBitIndex = 0; firstBitIndex < 64; firstBitIndex++) {
long firstBit = 1L << firstBitIndex;
if (firstBit >= n)
break;
for (int secondBitIndex = firstBitIndex + 1; secondBitIndex < 64; secondBitIndex++) {
long value = firstBit | (1L << secondBitIndex);
if (value > n)
break;
sum += value;
}
}
System.out.println(sum % 1000000007);
sc.close();
}
}
@JoopEggen你说的对,我忘了“L”。我修改了代码。无论如何,人们必须非常小心,因为最后一位会切换符号,这肯定会干扰> n比较。因此,悲伤的Java没有适当的无符号类型... –
关于符号:N = 10^18 = 10^3^6
@JoopEggen哦,是的,忘了这一点 –
[看看这个(HTTPS:/ /en.wikipedia.org/wiki/Sieve_of_Eratosthenes) – SMA
你刚刚编辑了你问的问题,使它成为一个完全不同的问题? –
我首先输入了一个错误的问题Leo,请帮助我解决这个问题。 – sagnikDas