Hướng dẫn cho Dòng sông Nile

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: Thiencohoc2012

Solution

Sub 1

Ý tưởng

Xây 1 hàm kiểm tra số nguyên tố.
Duyệt xâu và tách ra thành các đoạn liên tiếp chỉ gồm số.
Sử dụng stoll để chuyển xâu sang số.
Kiểm tra số nguyên tố.
Tính tổng (mỗi số nguyên tố hợp lệ % 4).
Cuối cùng in ra kết quả dựa trên 2 trường hợp đã chia.

Độ phức tạp

Hàm kiểm tra nguyên tố: \(O(N)\)
Duyệt xâu: \(O(|S|)\)
Tổng: \(O(|S| + k \cdot N)\)

\(|S|\) : độ dài xâu S
\(k\) : số đoạn tìm được
\(N \le 5 \times 10^6\)

Code mẫu 1

C++

// Author : Thiên Cơ Học
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e6;
bool prime(ll n)
{
    if (n < 2) return false;
    for (ll i = 2; i < n; i++)
    {
        if (n % i == 0) return false;
    }
    return true;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    string s;
    cin >> s;
    ll tong = 0;
    ll n = s.size();
    for (ll i = 0; i < n;)
    {
        if (!isdigit(s[i]))
        {
            i++;
            continue;
        }

        string t = "";
        while (i < n && isdigit(s[i]))
        {
            t += s[i];
            i++;
        }
        ll x = stoll(t);
        if (x <= N && prime(x))
        {
            tong += x % 4;
        }
    }
    if (tong % 2 == 0)
    {
        cout << 2;
    }
    else
    {
        cout << 1;
    }
}

Sub 2

Ý tưởng

Xây dựng 1 hàm kiểm tra số nguyên tố tối ưu hoặc 1 hàm sàng nguyên tố.
Duyệt xâu S đồng thời sử dụng mảng t để lưu các đoạn số liên tiếp.
Duyệt mảng t và lưu các đoạn số hợp lệ vào mảng m.
Tính tổng (mỗi số nguyên tố hợp lệ % 4).
In ra kết quả bài toán dựa trên kết quả chia dư với 2.

Độ phức tạp

Hàm kiểm tra nguyên tố: \(O(\sqrt{N})\)
Duyệt xâu: \(O(|S|)\)
Tổng: \(O(|S| + k\sqrt{N})\)

\(|S|\) : độ dài xâu S
\(k\) : số đoạn tìm được
\(N \le 5 \times 10^6\)

Code mẫu 2

C++

// Author : Thiên Cơ Học
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e6 + 5;
bool prime(ll n) 
{
    if(n < 2) return false;
    if(n == 2 || n == 3) return true;
    if(n % 2 == 0 || n % 3 == 0) return false;
    for(ll i = 5; i * i <= n; i += 6) 
    {
        if(n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    string s;
    cin >> s;
    ll n = s.size();
    vector<string> t;
    for (ll i = 0; i < n; )
    {
        if (!isdigit(s[i]))
        {
            i++;
            continue;
        }
        string p = "";
        while (i < n && isdigit(s[i]))
        {
            p += s[i];
            i++;
        }
        t.push_back(p);   
    }
    n = t.size();
    vector<ll> m;
    for (ll i = 0 ; i < n; i++)
    {
        if (t[i].size() > 18) 
        {
            continue;
        }
        ll q = stoll(t[i]);

        if (q < N && prime(q))
        { 
            m.push_back(q);
        }
    }
    ll tong = 0;
    for (ll i = 0; i < m.size(); i++)
    {
        tong += m[i] % 4;
    }
    if (tong % 2 == 0)
    {
        cout << 2;
    }
    else
    {
        cout << 1;
    }
}

Bình luận

Tải bình luận...

Không có bình luận nào.