Hướng dẫn cho Mặt nạ nguyên tố

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: Prototype

Hướng dẫn giải: Mặt nạ nguyên tố

Phân tích

Với mỗi số \( n \), gọi các ước nguyên tố phân biệt là:
\( p_1, p_2, ..., p_k \), với \( k \ge 2 \)

Đặt:

\[ S = p_1 + p_2 + \cdots + p_k \]
\[ P = p_1 \cdot p_2 \cdots p_k \]

Điều kiện:

  • \( P \mod S = 0 \)
  • \( Q = \frac{P}{S} \) là số nguyên tố

Nhận xét

Chỉ xét prime phân biệt, không quan tâm số mũ

Sub 1 (25%)

Ý tưởng

  • Duyệt từng số
  • Phân tích thừa số bằng chia thử
  • Lấy tập prime
  • Tính \( S, P \)

Code C++

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

bool isPrime(int x){
    if(x < 2) return false;
    for(int i = 2; i * i <= x; i++)
        if(x % i == 0) return false;
    return true;
}

int main(){
    int T; cin >> T;
    while(T--){
        int L, R; cin >> L >> R;
        int ans = 0;

        for(int n = L; n <= R; n++){
            int x = n;
            set<int> primes;

            for(int i = 2; i * i <= x; i++){
                if(x % i == 0){
                    primes.insert(i);
                    while(x % i == 0) x /= i;
                }
            }
            if(x > 1) primes.insert(x);

            if(primes.size() < 2) continue;

            long long P = 1;
            int S = 0;

            for(int p : primes){
                P *= p;
                S += p;
            }

            if(P % S == 0){
                int Q = P / S;
                if(isPrime(Q)) ans++;
            }
        }

        cout << ans << '\n';
    }
}

Sub 2 (25%)

Ý tưởng

Dùng SPF để phân tích nhanh mỗi số

Code C++

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

const int MAXN = 5000000;
int spf[MAXN + 1];

void sieve(){
    for(int i = 1; i <= MAXN; i++) spf[i] = i;

    for(int i = 2; i * i <= MAXN; i++){
        if(spf[i] == i){
            for(int j = i * i; j <= MAXN; j += i)
                if(spf[j] == j) spf[j] = i;
        }
    }
}

bool isPrime(int x){
    if(x < 2) return false;
    for(int i = 2; i * i <= x; i++)
        if(x % i == 0) return false;
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    sieve();

    int T; cin >> T;
    while(T--){
        int L, R; cin >> L >> R;
        int ans = 0;

        for(int n = L; n <= R; n++){
            int x = n;
            set<int> primes;

            while(x > 1){
                primes.insert(spf[x]);
                x /= spf[x];
            }

            if(primes.size() < 2) continue;

            long long P = 1;
            int S = 0;

            for(int p : primes){
                P *= p;
                S += p;
            }

            if(P % S == 0){
                int Q = P / S;
                if(isPrime(Q)) ans++;
            }
        }

        cout << ans << '\n';
    }
}

Sub 3 (25%)

Ý tưởng

Precompute tất cả số hợp lệ và dùng prefix sum

Code Python

Python
MAXN = 100000

spf = list(range(MAXN + 1))
for i in range(2, int(MAXN**0.5) + 1):
    if spf[i] == i:
        for j in range(i*i, MAXN+1, i):
            if spf[j] == j:
                spf[j] = i

is_prime = [True]*(MAXN+1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(MAXN**0.5)+1):
    if is_prime[i]:
        for j in range(i*i, MAXN+1, i):
            is_prime[j] = False

pref = [0]*(MAXN+1)

for n in range(1, MAXN+1):
    x = n
    primes = set()

    while x > 1:
        primes.add(spf[x])
        x //= spf[x]

    ok = False

    if len(primes) >= 2:
        P = 1
        S = 0
        for p in primes:
            P *= p
            S += p

        if P % S == 0:
            Q = P // S
            if Q <= MAXN and is_prime[Q]:
                ok = True

    pref[n] = pref[n-1] + (1 if ok else 0)

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    L, R = map(int, input().split())
    print(pref[R] - pref[L-1])

Sub 4 (100%)

Ý tưởng

Sieve nâng cao: đẩy thông tin từ prime xuống bội

Code C++

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

const int MAX_VAL = 5000000;
int sum_primes[MAX_VAL + 1];
long long prod_primes[MAX_VAL + 1];
int count_primes[MAX_VAL + 1];
bool is_prime[MAX_VAL + 1];
int prefix_sum[MAX_VAL + 1];

void precompute() {
    fill(is_prime + 2, is_prime + MAX_VAL + 1, true);

    for (int i = 1; i <= MAX_VAL; ++i)
        prod_primes[i] = 1;

    for (int i = 2; i <= MAX_VAL; ++i) {
        if (is_prime[i]) {
            for (int j = i; j <= MAX_VAL; j += i) {
                if (j > i) is_prime[j] = false;

                sum_primes[j] += i;
                count_primes[j]++;

                if (prod_primes[j] != -1) {
                    if (prod_primes[j] > MAX_VAL / i + 1)
                        prod_primes[j] = -1;
                    else
                        prod_primes[j] *= i;
                }
            }
        }
    }

    for (int n = 1; n <= MAX_VAL; ++n) {
        bool ok = false;

        if (count_primes[n] >= 2) {
            int S = sum_primes[n];
            long long P = prod_primes[n];

            if (P != -1 && P % S == 0) {
                int Q = P / S;
                if (Q <= MAX_VAL && is_prime[Q]) {
                    ok = true;
                }
            }
        }

        prefix_sum[n] = prefix_sum[n - 1] + (ok ? 1 : 0);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    precompute();

    int T;
    cin >> T;
    while (T--) {
        int L, R;
        cin >> L >> R;
        cout << prefix_sum[R] - prefix_sum[L - 1] << '\n';
    }
}

Code Python (Sub 4 - Full AC)

Python
import sys
input = sys.stdin.readline

MAX = 5000000

sum_primes = [0] * (MAX + 1)
prod_primes = [1] * (MAX + 1)
count_primes = [0] * (MAX + 1)
is_prime = [True] * (MAX + 1)
prefix_sum = [0] * (MAX + 1)

is_prime[0] = is_prime[1] = False

# sieve + cập nhật
for i in range(2, MAX + 1):
    if is_prime[i]:
        for j in range(i, MAX + 1, i):
            if j > i:
                is_prime[j] = False

            sum_primes[j] += i
            count_primes[j] += 1

            if prod_primes[j] != -1:
                if prod_primes[j] > MAX // i + 1:
                    prod_primes[j] = -1
                else:
                    prod_primes[j] *= i

# prefix
for n in range(1, MAX + 1):
    ok = False

    if count_primes[n] >= 2:
        S = sum_primes[n]
        P = prod_primes[n]

        if P != -1 and P % S == 0:
            Q = P // S
            if Q <= MAX and is_prime[Q]:
                ok = True

    prefix_sum[n] = prefix_sum[n - 1] + (1 if ok else 0)

# query
T = int(input())
for _ in range(T):
    L, R = map(int, input().split())
    print(prefix_sum[R] - prefix_sum[L - 1])

Code Java (Sub 4)

Java
import java.util.*;

public class Main {
    static final int MAX = 5000000;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int[] sum = new int[MAX+1];
        long[] prod = new long[MAX+1];
        int[] cnt = new int[MAX+1];
        boolean[] isPrime = new boolean[MAX+1];
        int[] pref = new int[MAX+1];

        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        Arrays.fill(prod, 1);

        for(int i=2;i<=MAX;i++){
            if(isPrime[i]){
                for(int j=i;j<=MAX;j+=i){
                    if(j>i) isPrime[j]=false;

                    sum[j]+=i;
                    cnt[j]++;

                    if(prod[j]!=-1){
                        if(prod[j] > MAX / i + 1) prod[j] = -1;
                        else prod[j]*=i;
                    }
                }
            }
        }

        for(int n=1;n<=MAX;n++){
            boolean ok=false;

            if(cnt[n]>=2){
                int S=sum[n];
                long P=prod[n];

                if(P!=-1 && P%S==0){
                    int Q=(int)(P/S);
                    if(Q<=MAX && isPrime[Q]) ok=true;
                }
            }

            pref[n]=pref[n-1]+(ok?1:0);
        }

        int T=sc.nextInt();
        while(T-- > 0){
            int L=sc.nextInt(), R=sc.nextInt();
            System.out.println(pref[R]-pref[L-1]);
        }
    }
}

Bình luận

Mới nhất
Tải bình luận...

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