Hướng dẫn giải của Bedao Mini Contest 17 - SUMSQUARE


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Nhận xét các giá trị của ~a~ và ~b~ đều không vượt quá ~sqrt(k)~ nên ta có thể duyệt qua mọi ~a~ từ ~0~ đến ~sqrt(k)~ rồi đếm xem có bao nhiêu ~a~ có ~b~ nguyên phù hợp với ~a~ đó .

Code mẫu

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
typedef long long ll;
typedef pair<ll, ll> ii;

const int N = 1e5 + 7, MOD = 1e9 + 7;
int n, a[N], f[N], g[N], num[N];
vector<int> adj[N];

int add(int x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
    return x;
}

int mul(int x, int y) {
    return 1ll * x * y % MOD;
}

int sub(int x, int y) {
    x -= y;
    if (x < 0) x += MOD;
    return x;
}

int fexp(int x, int y) {
    int ans = 1;
    for (; y; y >>= 1, x = mul(x, x))
        if (y & 1) ans = mul(ans, x);
    return ans;
}
int inv(int x) { return fexp(x, MOD - 2); }

ll k;

ll cal(long long k)
{
    int dem = 0 ;
    for(long long i=1; i*i <= k; i++)
    {
        long long x = k - i*i;
        x = sqrt(x);
        if(x*x + i*i == k) dem++;
    }
    return dem;
}

ll sumSquares(long long k)
{
    int ans = 0;
    if((long long) sqrt(k) * (long long) sqrt(k) == k) ans++;
    return ans + cal(k);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> k;
    cout << cal(k);
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.