Hướng dẫn giải của duong3982oj Contest 03 - Lại là lũy thừa
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ả:
Subtask 1: ~N \le 100~.
Với subtask này, chúng ta có thể dễ dàng được trọn vẹn số điểm, bằng cách for trâu các số ~x~, ~y~, ~z~, từ đó tính được số ~t~ và kiểm tra.
Độ phức tạp: ~O~ (~N^3~).
Subtask 2: ~N \le 10^5~.
Tiền xử lý: chúng ta sẽ lưu một pair <int, int> ~p_i~ là hai số ~a, b~ sao cho ~a^2 + b^2 = i~ (có thể không tồn tại).
Từ đó, dễ dàng phân tích ~N~ thành ~x, y~ bất kỳ mà ~x + y = N~ và ~p_x, p_y~ đều tồn tại, từ đó tìm ra kết quả.
Độ phức tạp: ~O~ (~N \times \sqrt N~).
Subtask 3: ~N~ là số chính phương.
Dễ thấy: kết quả của subtask này là bốn số: ~\sqrt N~, ~0~, ~0~, ~0~.
Độ phức tạp: ~O~ ~(1)~.
Subtask 5 : ~N~ ~=~ ~a^2~ ~+~ ~b^2~
Nguồn: Blog Codeforces.
Nhận xét: ~N~ chỉ có thể phân tích ra thành tổng ~2~ số chính phương khi biểu diễn thập phân của ~N~ ko có số nguyên tố ~p \equiv 3 (mod 4)~ với số mũ ~k~ lẻ
- Ta tìm 1 số ~c~ sao cho ~c^2 \equiv -1 (mod p)~
Để tìm ~c~ ta có thể random ~1~ số ~x~ trong khoảng ~[1, p - 1]~ sao cho ~x^{((p - 1)/2)} \equiv -1~ (~mod~ ~p~). Trong toán học số ~x~ được gọi là Thặng dư bậc ~2~ modulo ~p~ . Từ đó ta chỉ cần cho ~c = \sqrt x~ là xong (Tỉ lệ tìm ra được ~x~ rất lớn nên ko lo về độ phức tạp).
- Ta tìm ~gcd~ ~(n, z + i)~ (~i~ là số phức) và viết nó ra ~a + bi~ và ra được đáp án cho ~(a, b)~
Subtask 6: ~N \le 10^{18}~.
Theo định lý bốn số Lagrange, luôn tồn tại bốn số nguyên dương thỏa mãn đề bài.
1. Thuật toán tương đối (Chỉ dành cho bài này)
Với cách duyệt ở subtask ~1~, nếu ta break sớm có thể được khoảng ~50 \%~ số test.
Ta sẽ cải tiến như sau: Cố định số lớn nhất chỉ nằm trong khoảng ~[\sqrt N - 500, \sqrt N]~.
Tương tự với các số lớn nhì, lớn ba.
Bằng cách này, ta có thể qua mọi test.
Độ phức tạp: ~O~ (~500^3~).
Code mẫu:
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
signed main (){
ios_base::sync_with_stdio (false);
cin.tie (NULL);
cout.tie (NULL);
cin >> n;
int tmp1 = 0, tmp2 = 0, tmp3 = 0, tmp4 = 0;
for (int i = sqrt (n); i >= sqrt (n) - 50; i--){
int cc = n - i * i;
cc = sqrt (cc);
for (int j = min (cc, i); j >= cc - 50 && j >= 0; j--){
cc = n - i * i - j * j; cc = sqrt (cc);
for (int k = min (cc, j); k >= cc - 50 && k >= 0; k--){
int val = n - i * i - j * j - k * k;
int x = sqrt (val);
if (abs (x * x - val) == 1){
tmp1 = i; tmp2 = j; tmp3 = k; tmp4 = x;
} else if (abs (x * x - val) == 0){
cout << i << ' ' << j << ' ' << k << ' ' << x; exit (0);
}
}
}
}
cout << tmp1 << ' ' << tmp2 << ' ' << tmp3 << ' ' << tmp4;
}
2. Thuật toán chuẩn (Thuật này được viết trong một bài nghiên cứu ( Rabin Shallit ) với giá 15$. Mong các bạn ko phân phát code bừa bãi 🐧)
Ta sẽ chia trường hợp như sau
TH1: ~N~ là số chính phương
Vì ~N~ là số chính phương nên ta chỉ cần return ~{sqrt(n),0,0,0}~
TH2: ~N = 4k~
Vì ~N = 4k~ nên ta sẽ tìm đáp án cho ~N/4~ và nhân 2 lên cho từng hạng tử
TH3: ~N = 8k+7~
Khi ~N = 8k+7~ ta có thể tách ~N-4~ ra làm tổng 3 số chính phương (Thuật toán ở dưới) và cho số còn lại = ~2~
TH4: Còn lại.
Ta chắc chắn có thể tách ~N~ ra làm tổng 3 số chính phương
Đến đây ta có thể dễ dàng code đoạn trên bằng đệ quy (Độ phức tạp sẽ chỉ là ~log_4(n)~) việc còn lại là viết hàm tách N ra làm 3 số chính phương
Đến đây ta cũng chia làm các trường hợp như sau
- TH1: ~N~ là số chính phương.
Vì ~N~ là số chính phương nên ta chỉ cần return ~{\sqrt n, 0, 0, 0}~
- TH2: ~N = 4k~.
Vì ~N = 4k~ nên ta sẽ tìm đáp án cho ~N/4~ và nhân ~2~ lên cho từng hạng tử.
- TH3: Còn lại.
Ta chắc chắn sẽ tìm được cách để phân tích ~N~ ra 1 số ~x^2 + p~ hoặc ~x^2 + 2p~ với ~p~ là 1 số nguyên tố ở dạng ~4k+1~ (lại 1 lần nữa để tìm ~x~ thì chỉ còn cách random 😁).
Theo Định lý Fermat về tổng 2 số chính phương ta biết được ~p~ luôn tách được ra thành tổng 2 số chính phương.
Việc tách ~p~ ra làm 2 số chính phương sẽ đơn giản hơn 1 chút nếu ~p~ là số nguyên tố chia ~4~ dư ~1~.
Ta có ~a^2~ + ~b^2~ = ~p~ tương đương với ~(a + cb)(a - cb) = p~ với ~c~ được định nghĩa ở Sub 5. Đến đây thực ra ta chỉ cần tìm ~b~ sao cho ~cb~ chia dư ~p~ ra 1 số < ~\sqrt p~ và chọn ~a~ là số dư.
#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 jdg(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){
assert(l <= r);
return uniform_int_distribution<int>(l,r)(jdg);
}
bool isSquare(int n){
int s = sqrtl(n);
return s*s == n;
}
using u64 = uint64_t;
using u128 = __uint128_t;
u64 binpower(u64 base, u64 e, u64 mod) {
u64 result = 1;
base %= mod;
while (e) {
if (e & 1)
result = (u128)result * base % mod;
base = (u128)base * base % mod;
e >>= 1;
}
return result;
}
bool check_composite(u64 n, u64 a, u64 d, int s) {
u64 x = binpower(a, d, n);
if (x == 1 || x == n - 1)
return false;
for (int r = 1; r < s; r++) {
x = (u128)x * x % n;
if (x == n - 1)
return false;
}
return true;
};
bool MillerRabin(u64 n){
if (n < 2) return false;
int r = 0;
u64 d = n - 1;
while ((d & 1) == 0) {
d >>= 1;
r++;
}
for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
if (n == a)
return true;
if (check_composite(n, a, d, r))
return false;
}
return true;
}
map<int, tuple<int,int,int,int>> RABIN_EXCEPTIONS = {
{5, {2LL, 1LL, 0LL, 0LL}},
{10, {3LL, 1LL, 0LL, 0LL}},
{13, {3LL, 2LL, 0LL, 0LL}},
{34, {5LL, 3LL, 0LL, 0LL}},
{37, {6LL, 1LL, 0LL, 0LL}},
{58, {7LL, 3LL, 0LL, 0LL}},
{61, {6LL, 5LL, 0LL, 0LL}},
{85, {9LL, 2LL, 0LL, 0LL}},
{130, {11LL, 3LL, 0LL, 0LL}},
{214, {14LL, 3LL, 3LL, 0LL}},
{226, {15LL, 1LL, 0LL, 0LL}},
{370, {19LL, 3LL, 0LL, 0LL}},
{526, {21LL, 9LL, 2LL, 0LL}},
{706, {25LL, 9LL, 0LL, 0LL}},
{730, {27LL, 1LL, 0LL, 0LL}},
{829, {27LL, 10LL, 0LL, 0LL}},
{1414, {33LL, 18LL, 1LL, 0LL}},
{1549, {35LL, 18LL, 0LL, 0LL}},
{1906, {41LL, 15LL, 0LL, 0LL}},
{2986, {45LL, 31LL, 0LL, 0LL}},
{7549, {85LL, 18LL, 0LL, 0LL}},
{9634, {97LL, 15LL, 0LL, 0LL}},
};
vector<int> getRemain(int a, int b, int bound) {
int lim = sqrtl(bound);
vector<int> res;
while(b){
int r = a%b;
if (r <= lim) res.push_back(r);
a = b;
b = r;
}
return res;
}
tuple<int,int,int,int> twoSquare(int p) {
if(p == 1) return {1,0,0,0};
if(p == 2) return {1,1,0,0};
vector<int> rem;
do{
int q = rand(1,p);
while (binpower(q,(p-1)/2,p) != p-1) q = rand(1,p);
int x = binpower(q,(p-1)/4,p);
rem = getRemain(p,x,p);
}while(rem.size() <= 2);
return {rem[0],rem[1],0,0};
}
tuple<int,int,int,int> threeSquare(int n){
if(RABIN_EXCEPTIONS.find(n) != RABIN_EXCEPTIONS.end()) return RABIN_EXCEPTIONS[n];
if(n%4 == 0){
tuple<int,int,int,int> res = threeSquare(n/4);
get<0>(res) *= 2; get<1>(res) *= 2; get<2>(res) *= 2; get<3>(res) *= 2;
return res;
}
if(n%8 == 7) return {0,0,0,0};
if(n%8 == 3){
int x,p;
int lim = sqrtl(n);
do{
x = rand(1,lim);
p = (n-x*x)/2;
}while( (n-(x*x))%2 || !MillerRabin(p) );
tuple<int,int,int,int> res = twoSquare(p);
//cout << p << endl;
return {x,get<0>(res)+get<1>(res), abs(get<0>(res)-get<1>(res)),0};
}
if(isSquare(n)) return {sqrtl(n),0,0,0};
int x,p;
int lim = sqrtl(n);
do{
x = rand(1,lim);
p = (n-x*x);
}while( !MillerRabin(p) );
tuple<int,int,int,int> res = twoSquare(p);
return {x,get<0>(res),get<1>(res),0};
}
tuple<int,int,int,int> fourSquare(int n){
if(n == 1) return {1,0,0,0};
if(n == 2) return {1,1,0,0};
if(n == 3) return {1,1,1,0};
if(n%4 == 0){
tuple<int,int,int,int> res = fourSquare(n/4);
get<0>(res) *= 2; get<1>(res) *= 2; get<2>(res) *= 2; get<3>(res) *= 2;
return res;
}
if(isSquare(n)){
return {sqrtl(n),0,0,0};
}
if(n%8 == 7){
tuple<int,int,int,int> res =threeSquare(n-4);
return {2,get<0>(res), get<1>(res), get<2>(res)};
}
return threeSquare(n);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
auto res = fourSquare(n);
cout << get<0>(res) << ' ' << get<1>(res) << ' ' << get<2>(res) << ' ' << get<3>(res);
return 0;
}
Bình luận