[leetcode每日一题] 633. 平方数之和

yyyyye

简单枚举
时间复杂度：$O(\sqrt{c})$
空间复杂度：$O(1)$

class Solution {
public:
    bool judgeSquareSum(int c) {
        for(int i = 0; 1LL * i * i <= 1LL * c; i++)
        {
            if(sqrt(c - i * i) == (int)sqrt(c - i * i))
                return true;
        }
        return false;
    }
};

If_you_love

~~纯暴力~~很有技巧，思考量很大，有惊无险拿下

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (int i=sqrt(c);i>=0;i--)
        {
            int d=c-i*i;
            if(sqrt(d)==(int)sqrt(d))
            {
                return true;
            }
        }
        return false;
    }
};

时间复杂度：O(sqrt(c)；空间复杂度：O(1)

dqw

数论。费马平方和定理。

费马平方和 : 奇质数能表示为两个平方数之和的充分必要条件是该质数被 4 除余 1 。
翻译过来就是：当且仅当一个自然数的质因数分解中，满足 4k+3 形式的质数次方数均为偶数时，该自然数才能被表示为两个平方数之和。

因此我们对 c 进行 Pollard-Rho 质因数分解，再判断满足 4k+3 形式的质因子的次方数是否均为偶数即可。期间可使用32位快速 Miller-Rabin 算法并使用SplitMix32自定义哈希加快umap存储优化。

时间复杂度：$O(\log (c))$ —— 全Lc站最低复杂度，执行0ms
空间复杂度：$O(\log (c))$

class Solution {
public:
    struct Hash {
        static uint32_t splitmix32(uint32_t x) {
            x += 0x9e3779b;
            x = (x ^ (x >> 15)) * 0xbf58476;
            x = (x ^ (x >> 13)) * 0x94d049b;
            return x ^ (x >> 14);
        }
        size_t operator()(uint32_t x) const {
            static const uint32_t FIXED_RANDOM = rand();
            return splitmix32(x + FIXED_RANDOM);
        }
    };
    int fastgcd(int a, int b) {
        if (!a || !b)
            return a | b;
        unsigned shift = __builtin_ctz(a | b);
        a >>= __builtin_ctz(a);
        do {
            b >>= __builtin_ctz(b);
            if (a > b)
                swap(a, b);
            b -= a;
        } while (b);
        return a << shift;
    }
    int qpow(int a, int b, int m) {
        int ret = 1;
        while (b) {
            if (b & 1)
                ret = (long long)ret * a % m;
            b >>= 1;
            a = (long long)a * a % m;
        }
        return ret;
    }
    bool MillerRabin(int n) {
        if (n < 3 or n % 2 == 0)
            return n == 2;
        if (n % 3 == 0)
            return n == 3;
        int u = n - 1, t = 0;
        while (u % 2 == 0)
            u /= 2, ++t;
        int dict[] = {2, 7, 61};
        for (int a : dict) {
            if (a % n <= 1)
                return 1;
            int v = qpow(a, u, n);
            if (v == 1)
                continue;
            int s;
            for (s = 0; s < t; ++s) {
                if (v == n - 1)
                    break;
                v = (long long)v * v % n;
            }
            if (s == t)
                return 0;
        }
        return 1;
    }
    int PollardRho(int x) {
        int s = 0, t = 0, c = rand() % (x - 1) + 1;
        int step = 0, goal = 1, val = 1;
        for (goal = 1;; goal <<= 1, s = t, val = 1) {
            for (step = 1; step <= goal; ++step) {
                t = ((long long)t * t + c) % x;
                val = (long long)val * abs(t - s) % x;
                if (step % 127 == 0) {
                    int d = fastgcd(val, x);
                    if (d > 1)
                        return d;
                }
            }
            int d = fastgcd(val, x);
            if (d > 1)
                return d;
        }
    }
    vector<int> getfac(int x) {
        vector<int> fac;
        unordered_map<int, int, Hash> primes;
        function<void(int)> get = [&](int x) {
            if (x < 2) {
                return;
            }
            if (MillerRabin(x)) {
                primes[x]++;
                return;
            }
            int mx = PollardRho(x);
            get(x / mx);
            get(mx);
        };
        get(x);
        vector<pair<int, int>> tmp(primes.begin(), primes.end());
        int sz = tmp.size();
        function<void(int, int)> dfs = [&](int id, int x) {
            if (id == sz) {
                fac.push_back(x);
                return;
            }
            int p = 1;
            for (int i = 0; i <= tmp[id].second; i++) {
                if (i != 0) {
                    p *= tmp[id].first;
                }
                dfs(id + 1, x * p);
            }
        };
        dfs(0, 1);
        sort(fac.begin(), fac.end());
        return fac;
    }
    bool judgeSquareSum(int c) {
        vector<int> fac = getfac(c);
        for (int i : fac) {
            if (i == 1 or c % i)
                continue;
            int exp = 0;
            while (c % i == 0) {
                c /= i;
                exp++;
            }
            if (i % 4 == 3 and exp & 1)
                return false;
        }
        return c % 4 != 3;
    }
};

ygxdsh

bool judgeSquareSum(int c) {
        for(int i=0;i<=sqrt(c);i++)
        {
            if(sqrt(c-i*i)==int(sqrt(c-i*i))) return true;
        }
        return false;
    }

Godwit

就是一个从0开始的遍历过程,注意i<=sqrt(c),否则会爆时间

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (int i=0;i<=sqrt(c);i++){
            if (sqrt(c-i*i)==(int)sqrt(c-i*i))
                return true;
        }
        return false;
    }
};

xxingyu

what can i say

/*
 * @lc app=leetcode.cn id=633 lang=cpp
 *
 * [633] 平方数之和
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution {
 public:
  using i64 = long long;
  bool judgeSquareSum(int c) {
    bool f = false;
    for (i64 i = 0; i * i <= c; ++i) {
      i64 res = (i64)sqrt(c - i * i);
      if (res * res + i * i == c) {
        f = true;
        break;
      }
    }
    return f;
  }
};
// @lc code=end

If_you_love

xxingyu 曼巴，out

ssssshi

简单平方数，优化下防止爆时间就成

class Solution {
public:
    bool judgeSquareSum(int c) {
        for(long long i=0;i*i<=c;i++)
        {
            if(sqrt(c-i*i)==(int)(sqrt(c-i*i)))
            {
                return true;
            }
        }
        return false;
    }
};

Koarz

class Solution {
public:
    bool judgeSquareSum(int c) {
        if (c == 0) return true;
        for (long long i = 1; i * i <= c; i++) {
            int v = c - i * i;
            int b = sqrt(v);
            if (b * b == v) {
                return true;
            }
        }
        return false;
    }
};

Future

public:
    bool judgeSquareSum(int c) {
        for(long long i=0;i<=sqrt(c);i++)
        {
           long long b=c-i*i;
           int sign=sqrt(b);
           if(sign*sign==b)
           {
            return true;
           }
        }
        return false;
    }
};

xujingyuan

不开long long可能会溢出（执行出错）；用俩循环但是超出时间限制（可能是循环没写对）；这样写能过。

bool judgeSquareSum(int c) {
for( long long int i=0;i*i<=c;i++)
{
   double a=sqrt(c-i*i);
   if(a==(int)a)return true;
}
return false;
    }

tjp

简单题，要注意的点就一个long long。

public:
    bool judgeSquareSum(int c) {
        int s;double b;int n;int cnt = 0;string arr;
    
    for (long long i = 0;i*i <=c;i++)
    {
        s = c - i * i;
        b = sqrt(s);n = b;
        if (s == n * n ) 
            return true;
        
    }
    return false;
    }
};

wszyh

开long long（好像int也行），然后用sqrt缩短一下，判断b是不是整数然后返回1或0

public:
    bool judgeSquareSum(int c) {
        for(long long a=0;a<=sqrt(c);a++){
            double b=sqrt(c-a*a);
            if(b==(int)b) 
            return 1;
        }
        return 0;
    }
};

发表情包召唤

开long long，压缩循环小心超时

public:
    bool judgeSquareSum(int c) {
        for(long long i=0;i*i<=c;i++)
        {
        long long j=sqrt(c-i*i);
        if(j*j+i*i==c)
        return true;
        }
        return false;
    }
};```

RiVER

屌丝纯暴力做法

class Solution {
public:
    bool judgeSquareSum(int c) {
        for(long long i=0;i*i<=c;i++)
        {
            if(sqrt(c-i*i)==(int)(sqrt(c-i*i)))
                return true;
        }
        return false;
    }
};