logoChat01.ai

## Special Number Diego, who is a computer scienc...

Créé le : 31 juillet 2026

Répondu en utilisant GPT-5.6 Thinking par Chat01

Question

Special Number

Diego, who is a computer science student learning encryption algorithms for fun, has decided to come up with his own simple encryption algorithm.

In Diego's algorithm, to obtain a private key, he provides the system with two numbers X and Y, and the private key is a set of all special numbers that lie in the range [X, Y].

Special Number

A special number is a number that:

  • Has exactly two factors.
  • Contains any or all of the digits of N in it.

Since Diego has very little coding experience, he has come to you for help in generating all the special numbers in the range X to Y.

Your task is to read the input from STDIN and write the output to STDOUT. Do not print any unnecessary strings while reading input or writing output.

Constraints

  • X, Y > 1
  • X < Y

Input Format

  • The first line contains two integers X and Y, separated by a single space.
  • The second line contains an integer N.

Output Format

Print all the special numbers in the range [X, Y] that contain any or all of the digits present in N.

The numbers must be printed:

  • in ascending order,
  • separated by a single space.

Sample Input 1

text
23 110
7

Sample Output 1

text
37 47 67 71 73 79 97 107

Explanation 1

For the range 23 to 110, the numbers having exactly two factors (prime numbers) are:

text
23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109

Among these, the numbers containing the digit 7 are:

text
37, 47, 67, 71, 73, 79, 97, 107

Hence the output is:

text
37 47 67 71 73 79 97 107

Sample Input 2

text
19 113
13

Sample Output 2

text
19 23 31 37 41 43 53 61 71 73 83 101 103 107 109 113

Explanation 2

For the range 19 to 113, the prime numbers are:

text
19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113

Numbers containing 1 are:

text
19, 31, 41, 61, 71, 101, 107, 109, 113

Numbers containing 3 are:

text
23, 31, 37, 43, 53, 73, 83, 103, 113

Taking the union of the above sets (numbers containing 1 or 3) gives:

text
19 23 31 37 41 43 53 61 71 73 83 101 103 107 109 113

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

bool prime(int n)
{
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; 1LL * i * i <= n; i += 2)
    {
        if (n % i == 0) return false;
    }
    return true;
}

bool ok(int x, int n)
{
    bool d[10] = {0};
    if (n == 0) d[0] = true;
    while (n)
    {
        d[n % 10] = true;
        n /= 10;
    }

    if (x == 0) return d[0];

    while (x)
    {
        if (d[x % 10]) return true;
        x /= 10;
    }
    return false;
}

void findSpecialNumber(int X, int Y, int N)
{
    bool first = true;
    for (int i = X; i <= Y; i++)
    {
        if (prime(i) && ok(i, N))
        {
            if (!first) cout << " ";
            cout << i;
            first = false;
        }
    }
}

Thus code passes 11/12 fix this

Réflexion

The filtering logic is correct; the likely failing case is performance or integer overflow at the upper bound. I’ll replace repeated primality tests with a segmented sieve and use 64-bit integers.

Worked for 17s

Réponse

Your digit-checking logic is correct. The likely hidden failure is caused by:

  1. Testing every number independently in O(n)O(\sqrt n), which may time out for a large interval.
  2. Using int, where i++ overflows when Y == INT_MAX.
  3. Not printing a final newline, which some strict judges may expect.

Use a segmented sieve and long long:

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

bool containsRequiredDigit(long long value, const array<bool, 10>& required)
{
    while (value > 0)
    {
        if (required[value % 10])
            return true;

        value /= 10;
    }

    return false;
}

void findSpecialNumber(long long X, long long Y, const string& N)
{
    array<bool, 10> required{};
    for (char digit : N)
        required[digit - '0'] = true;

    long long limit = static_cast<long long>(sqrtl(static_cast<long double>(Y)));

    // Correct possible floating-point rounding.
    while ((__int128)(limit + 1) * (limit + 1) <= Y)
        ++limit;

    while ((__int128)limit * limit > Y)
        --limit;

    // Find all primes up to sqrt(Y).
    vector<char> isPrime(limit + 1, true);

    if (limit >= 0)
        isPrime[0] = false;
    if (limit >= 1)
        isPrime[1] = false;

    vector<int> basePrimes;

    for (long long i = 2; i <= limit; ++i)
    {
        if (!isPrime[i])
            continue;

        basePrimes.push_back(static_cast<int>(i));

        if (i * i <= limit)
        {
            for (long long multiple = i * i;
                 multiple <= limit;
                 multiple += i)
            {
                isPrime[multiple] = false;
            }
        }
    }

    constexpr long long BLOCK_SIZE = 1'000'000;
    bool first = true;

    for (long long low = X; low <= Y;)
    {
        long long high = low + min(BLOCK_SIZE - 1, Y - low);
        vector<char> segment(high - low + 1, true);

        for (long long prime : basePrimes)
        {
            if ((__int128)prime * prime > high)
                break;

            long long quotient = low / prime + (low % prime != 0);
            __int128 firstMultiple = (__int128)quotient * prime;
            __int128 primeSquare = (__int128)prime * prime;

            firstMultiple = max(firstMultiple, primeSquare);

            if (firstMultiple > high)
                continue;

            for (long long multiple = static_cast<long long>(firstMultiple);
                 multiple <= high;
                 multiple += prime)
            {
                segment[multiple - low] = false;
            }
        }

        for (long long number = low; number <= high; ++number)
        {
            if (number >= 2 &&
                segment[number - low] &&
                containsRequiredDigit(number, required))
            {
                if (!first)
                    cout << ' ';

                cout << number;
                first = false;
            }
        }

        if (high == Y)
            break;

        low = high + 1;
    }

    cout << '\n';
}

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

    long long X, Y;
    string N;

    cin >> X >> Y;
    cin >> N;

    findSpecialNumber(X, Y, N);

    return 0;
}

This changes the approximate complexity from

O((Y−X+1)Y)O((Y-X+1)\sqrt Y)

to

O(Ylog⁡log⁡Y+(Y−X+1)log⁡log⁡Y),O(\sqrt Y\log\log Y+(Y-X+1)\log\log Y),

which is substantially faster for large ranges.

Partager cette Q&R