AcWing 1221. 四平方和

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1221. 四平方和原题链接简单

作者：

小呆呆 , 2019-12-08 16:28:04 , 所有人可见 , 阅读 2869

16

1

算法分析

(与带分数的转换方法类似)

1、$a^2 + b^2 + c^2 + d^2 = n$可以转换成 $c^2 + d^2 = n - a^2 - b^2$
2、通过哈希表存储$c^2 + d^2$的值
3、枚举a和b，若$n - a^2 - b^2$在哈希表中存在，则表示一定存在c和d，满足方程

时间复杂度 $O(n^2)$

Java 代码

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    public static void solve(int n)
    {
        //1、预处理，使用哈希表记录c*c + d*d的值
        for(int i = 0;i * i * 2 <= n;i++)
            for(int j = i;i * i + j * j <= n;j ++)
                if(!map.containsKey(i * i + j * j))
                    map.put(i * i + j * j, i);
        //2、枚举a，b
        for(int i = 0;i * i * 4 <= n;i++)
            for(int j = i;(i * i + j * j) * 2 <= n;j++)
            {
                //若c^2 + d^2 = n - a^2 - b^2;
                if(map.containsKey(n - i * i - j * j))
                {
                    int c = map.get(n - i * i - j * j);
                    int d = (int) Math.sqrt(n - i * i - j * j - c * c);
                    System.out.println(i + " " + j + " " + c + " " + d + " ");
                    return;
                }
            }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        solve(n);
    }
}

7 评论

null_luo 2022-10-08 04:59

为啥以平方速度递增的的时间复杂度不是 O(√n)* O(√n) = O(n)

Dylans123 2022-03-11 21:41

文思涌 2021-02-10 20:13

大佬请问下我这哪错了呢？明明都是从小到大排序的，边界条件不同虽然不知道你的2或4的意义。我这100算的是0068，却不是000 10,实在找不出来了TT

        for(int c=0;c*c<=n;c++) {
            for(int d=c;c*c+d*d<=n;d++) {   
                if(!map.containsKey(c*c+d*d));
                map.put(c*c+d*d,c);
            }
        }
        for(int a=0;a*a<=n;a++) {
            for(int b=a;b*b+a*a<=n;b++) {
                if(map.containsKey(n-a*a-b*b)) {
                    int c=map.get(n-a*a-b*b);
                    int d=(int)Math.sqrt(n-a*a-b*b-c*c);
                    System.out.println(a+" "+b+" "+c+" "+d);
                    return;
                }
            }
        }