25 . P 217[USACO 1.5]回文素数Prime Palindromes

13614 ワード

标题解:これは洛谷の25番目のテーマで、この問題について、私の方法は少しLowで、第1の構造の回文数で、第2の素性のテスト(ACになりましたが、耻ずかしい感じがします).
ソースコード
#include 
#include 
#include 
#include 

using namespace std;

#define  DATA_TYPE    unsigned long long

DATA_TYPE The_Multiplication_Operator(DATA_TYPE a, DATA_TYPE b, DATA_TYPE mod)
{
    DATA_TYPE ans = 0;
    while (b)
    {
        if (b & 1)
        {
            b--;
            ans = (ans + a) % mod;
        }
        b /= 2;
        a = (a + a) % mod;
    }
    return ans;
}

DATA_TYPE Addition_Operator(DATA_TYPE a, DATA_TYPE b, DATA_TYPE mod)
{
    DATA_TYPE ans = 1;
    while (b)
    {
        if (b & 1)
        {
            ans = The_Multiplication_Operator(ans, a, mod);
        }

        b /= 2;
        a = The_Multiplication_Operator(a, a, mod);
    }
    return ans;
}

bool Inspection(DATA_TYPE a, DATA_TYPE n)
{
    DATA_TYPE tem = n - 1;
    int j = 0;
    while (tem % 2 == 0)
    {
        tem /= 2;
        j++;
    }

    DATA_TYPE x = Addition_Operator(a, tem, n);
    if (x == 1 || x == n - 1)
        return true;
    while (j--)
    {
        x = The_Multiplication_Operator(x, x, n);
        if (x == n - 1) return true;
    }

    return false;
}

bool Miller_Rabin(DATA_TYPE Target_Number)
{
    if (Target_Number == 2)
        return true;
    if (Target_Number < 2 || Target_Number % 2 == 0)
        return false;

    for (int i = 1; i <= 20; i++)
    {
        DATA_TYPE a = rand() % (Target_Number - 2) + 1;
        if (!Inspection(a, Target_Number))
            return false;
    }

    return true;
}

int main()
{
    int number = 0;
    unsigned long long a, b, c;
    cin >> a >> b;

    c = b;
    while (c != 0)
    {
        c /= 10;
        number++;
    }

    switch (number)
    {
    case 1:
    {
        if(a<=5)
            cout << "5" << endl;
        if(a<=7)
            cout << "7" << endl;

        break;
    }
    case 2:
    {
        if (a <= 5)
            cout << "5" << endl;
        if (a <= 7)
            cout << "7" << endl;
        if(a<=11)
            cout << "11" << endl;

        break;
    }
    case 3:
    {
        if (a <= 5)
            cout << "5" << endl;
        if (a <= 7)
            cout << "7" << endl;
        if (a <= 11)
            cout << "11" << endl;

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                long long palindrome = 100 * d1 + 10 * d2 + d1;
                if (palindrome>=a && palindrome <= b && Miller_Rabin(palindrome))
                    cout << palindrome << endl;
            }
        }

        break;
    }
    case 4:
    {
        if (a <= 5)
            cout << "5" << endl;
        if (a <= 7)
            cout << "7" << endl;
        if (a <= 11)
            cout << "11" << endl;

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                long long palindrome = 100 * d1 + 10 * d2 + d1;
                if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                    cout << palindrome << endl;
            }
        }

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                long long palindrome = 1000 * d1 + 100 * d2 + 10 * d2 + d1;
                if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                    cout << palindrome << endl;
            }
        }

        break;
    }
    case 5:
    {
        if (a <= 5)
            cout << "5" << endl;
        if (a <= 7)
            cout << "7" << endl;
        if (a <= 11)
            cout << "11" << endl;

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                long long palindrome = 100 * d1 + 10 * d2 + d1;
                if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                    cout << palindrome << endl;
            }
        }

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                long long palindrome = 1000 * d1 + 100 * d2 + 10 * d2 + d1;
                if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                    cout << palindrome << endl;
            }
        }

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                for (int d3 = 0; d3 <= 9; d3++)
                {
                    long long palindrome = 10000 * d1 + 1000 * d2 + 100 * d3 + 10 * d2 + d1;
                    if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                        cout << palindrome << endl;
                }
            }
        }

        break;
    }
    case 6:
    {
        if (a <= 5)
            cout << "5" << endl;
        if (a <= 7)
            cout << "7" << endl;
        if (a <= 11)
            cout << "11" << endl;

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                long long palindrome = 100 * d1 + 10 * d2 + d1;
                if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                    cout << palindrome << endl;
            }
        }

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                long long palindrome = 1000 * d1 + 100 * d2 + 10 * d2 + d1;
                if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                    cout << palindrome << endl;
            }
        }

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                for (int d3 = 0; d3 <= 9; d3++)
                {
                    long long palindrome = 10000 * d1 + 1000 * d2 + 100 * d3 + 10 * d2 + d1;
                    if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                        cout << palindrome << endl;
                }
            }
        }
        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                for (int d3 = 0; d3 <= 9; d3++)
                {
                    long long palindrome = 100000 * d1 + 10000 * d2 + 1000 * d3 + 100 * d3 + 10 * d2 + d1;
                    if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                        cout << palindrome << endl;
                }
            }
        }

        break;
    }
    case 7:
    {
        if (a <= 5)
            cout << "5" << endl;
        if (a <= 7)
            cout << "7" << endl;
        if (a <= 11)
            cout << "11" << endl;

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                long long palindrome = 100 * d1 + 10 * d2 + d1;
                if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                    cout << palindrome << endl;
            }
        }

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                long long palindrome = 1000 * d1 + 100 * d2 + 10 * d2 + d1;
                if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                    cout << palindrome << endl;
            }
        }

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                for (int d3 = 0; d3 <= 9; d3++)
                {
                    long long palindrome = 10000 * d1 + 1000 * d2 + 100 * d3 + 10 * d2 + d1;
                    if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                        cout << palindrome << endl;
                }
            }
        }
        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                for (int d3 = 0; d3 <= 9; d3++)
                {
                    long long palindrome = 100000 * d1 + 10000 * d2 + 1000 * d3 + 100 * d3 + 10 * d2 + d1;
                    if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                        cout << palindrome << endl;
                }
            }
        }

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                for (int d3 = 0; d3 <= 9; d3++)
                {
                    for (int d4 = 0; d4 <= 9; d4++)
                    {
                        long long palindrome = 1000000 * d1 + 100000 * d2 + 10000 * d3 + 1000 * d4 + 100 * d3 + 10 * d2 + d1;
                        if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                            cout << palindrome << endl;
                    }
                }
            }
        }

        break;
    }

    case 8:
    case 9:
    {
        if (a <= 5)
            cout << "5" << endl;
        if (a <= 7)
            cout << "7" << endl;
        if (a <= 11)
            cout << "11" << endl;

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                long long palindrome = 100 * d1 + 10 * d2 + d1;
                if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                    cout << palindrome << endl;
            }
        }

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                long long palindrome = 1000 * d1 + 100 * d2 + 10 * d2 + d1;
                if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                    cout << palindrome << endl;
            }
        }

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                for (int d3 = 0; d3 <= 9; d3++)
                {
                    long long palindrome = 10000 * d1 + 1000 * d2 + 100 * d3 + 10 * d2 + d1;
                    if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                        cout << palindrome << endl;
                }
            }
        }
        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                for (int d3 = 0; d3 <= 9; d3++)
                {
                    long long palindrome = 100000 * d1 + 10000 * d2 + 1000 * d3 + 100 * d3 + 10 * d2 + d1;
                    if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                        cout << palindrome << endl;
                }
            }
        }

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                for (int d3 = 0; d3 <= 9; d3++)
                {
                    for (int d4 = 0; d4 <= 9; d4++)
                    {
                        long long palindrome = 1000000 * d1 + 100000 * d2 + 10000 * d3 + 1000 * d4 + 100 * d3 + 10 * d2 + d1;
                        if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                            cout << palindrome << endl;
                    }
                }
            }
        }

        for (int d1 = 1; d1 <= 9; d1 += 2)
        {
            for (int d2 = 0; d2 <= 9; d2++)
            {
                for (int d3 = 0; d3 <= 9; d3++)
                {
                    for (int d4 = 0; d4 <= 9; d4++)
                    {
                        long long palindrome = 10000000 * d1 + 1000000 * d2 + 100000 * d3 + 10000 * d4 + 1000 * d4 + 100 * d3 + 10 * d2 + d1;
                        if (palindrome >= a && palindrome <= b && Miller_Rabin(palindrome))
                            cout << palindrome << endl;
                    }
                }
            }
        }

        break;
    }

    default:
        break;
    }
    
    system("pause");
    return 0;
}