gpt4 book ai didi

java - 可以写成两个平方和的数字

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:28:30 25 4
gpt4 key购买 nike

从数学原理:

A number N is expressible as a sum of 2 squares if and only if in the prime factorization of N, every prime of the form (4k+3) occurs an even number of times!

我所做的是预先计算所有 4k+3 数字并通过连续除法检查它的频率。

这个程序是按照约束条件写的:

1 < T <100
0 < N < 10 ^ 12

import java.util.Scanner;

public class TwoSquaresOrNot {
static int max = 250000;
static long[] nums = new long[max];

public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int i = 0; i < max; ++i)
nums[i] = 4 * i + 3;
while (T-- > 0) {
long n = sc.nextLong();
System.out.println((canWrite(n) ? "Yes" : "No"));
}
}

private static boolean canWrite(long n) {
// TODO Auto-generated method stub
for (int i = 0; i < nums.length; ++i) {//loop through all the numbers
if (nums[i] > n)
return true;
int count = 0;
while (n % nums[i] == 0) {
count++;
n /= nums[i];
}
if (count % 2 != 0)//check for odd frequency
return false;
}
return true;
}
}

但这似乎在 SPOJ 中不起作用网站。

我错过了什么吗?还是我做错了什么?

0也在这里面考虑。

Some valid cases are:

1 = 1^2 + 0^2
8 = 2^2 + 2^2

最佳答案

根据 OP 的评论进行编辑。

一些事情。第一:如果你正在寻找质因数分解,你可以在 > sqrt(n) 时停止,你不必一直走到 n。

所以你的代码应该是这样的:

private static boolean canWrite(long n) {
// TODO Auto-generated method stub
for (int i = 0; i < nums.length; ++i) {//loop through all the numbers
//FIRST CHANGE: Sqrt
if (nums[i] > Math.sqrt(n))
break;
int count = 0;
while (n % nums[i] == 0) {
//SECOND CHANGE: count as an array
count[i]++;
n /= nums[i];
}
}
//SECOND CHANGE: count as an array
for (int i=0; i<count.length; i++) {
if (count[i] %2 != 0) return false;
}
return true;
}

关于java - 可以写成两个平方和的数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32270349/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com