በአንድ ክልል ውስጥ የክልሎች ምርቶች


የችግር ደረጃ ጠንካራ
ውስጥ በተደጋጋሚ ተጠየቀ የተከማቸ ዴ ሻው ፍሪጅ ቻርጅ google የ SAP ላብራቶሪዎች Snapdeal ታይምስ በይነመረብ
ሰልፍ ሞዱል ሂሳብ የጥያቄ ችግር

የችግሩ መግለጫ

“በአንድ ረድፍ ውስጥ ያሉ የክልሎች ምርቶች” ችግር ከ 1 እስከ n እና ጥ የጥያቄዎች ብዛት ያካተተ የኢቲጀር ድርድር ይሰጥዎታል ይላል። እያንዳንዱ ጥያቄ ክልሉን ይይዛል። የችግሩ መግለጫው በሞዱሎ ኤም ስር በተጠቀሰው ክልል ውስጥ ምርቱን ለመፈለግ ይጠይቃል m የትኛውም ዋና ቁጥር ነው ፡፡

ለምሳሌ

arr[] = {1,2,3,4,5,6}

M = 131

Query = [1, 6], [2, 4]
65 24

ማስረጃ 

ከ 1 እስከ 6 ድረስ የክልሉ ምርት ሞዱሎ ሲተገበር 720 ነው 65 ትቶ 24 ይቀራል ፡፡

በአንድ ክልል ውስጥ የክልሎች ምርቶች

ቀረበ

እንደ ቁጥር እና እንደ መጨረሻ አንድ ቁጥር ክልል ተሰጥቶታል ቁጥር. በመሃል መካከል ባሉ ቁጥሮች ሁሉ የተሞላ ስለሆነ ይህንን ክልል ከግምት ውስጥ ማስገባት። የእኛ ተግባር በዚህ ክልል ውስጥ ያሉትን የቁጥሮች ቁጥሮች ምርት መፈለግ ነው ፡፡ እኛ ምርቱን እና ተገላቢጦቹን ምርት እናሰላለን ፣ ከዚያ በኋላ ላይ ጥያቄውን እንፈታዋለን ፣ በዚህ መሠረት የቅድመ ምርት እና ተገላቢጦሽ ምርትን በማስላት ሁለት ደረጃዎች ፣ በአንድ ጊዜ በርካታ ጥያቄዎችን እንፈታለን ፣ አናደርግም ጥያቄን ለመፍታት መላውን ስልተ ቀመር ማለፍ ያስፈልጋል።

በመጀመሪያ ፣ የድርሻውን ቅድመ-ምርት ያስሉ ፣ ማለትም ፣ ድርድርን ማለፍ አለብን እና በመጀመሪያ ፣ የተሰጠውን የድርድር የመጀመሪያ አካል ወደ ቅድመ-ምርት ድርድር የመጀመሪያ አካል መገልበጥ ያስፈልገናል። እኛ የተሰጠውን ድርድር ከመጀመሪያው ቦታ በማቋረጥ እና ከተሰጠው ድርድር እና የምርት ድርድር የቀደመውን ንጥረ ነገር ምርት እናከማቸዋለን ፣ ሞዱሉን ለማቆየት ያገኘነውን ምርት ሞዱሎ እናቆያለን እና ወደ ምርት ድርድር ያከማቹ።

በሚቀጥለው ደረጃ እኛ የተገላቢጦሽ ምርትን በማስላት ላይ እንሆናለን ፣ ከዚህ ጋር የክልሉን ተገላቢጦሽ ምርት ማለታችን ነው ፣ እንደዚህ ዓይነት ተቃራኒውን ምርት እስከ እስክ ኢንዴክስ ድረስ ካሰላሰልነው ተገላቢጦሽ ምርት የሁሉም ቁጥሮች ምርት ይሆናል ፡፡ ከክልል 0 እስከ i. በዚህ እኛ ጥያቄውን በቋሚ ጊዜ መፍታት እንችላለን ፡፡ እያንዳንዱን ጥያቄ ለመፍታት ተጨማሪ ጥረቶችን ማድረግ አያስፈልገንም ፡፡ አሁን ጥያቄውን ለመፍታት ከፈለግን የ ‹ፕሪፕራክት› [የቀኝ] እና የ ”PreInverseProduct [ግራ -1]” ምርትን እንመልሳለን ፡፡ ይህ የሚፈለግ መልስ ይሆናል ፡፡

ኮድ

በአንድ ሰልፍ ውስጥ የክልሎችን ምርቶች ለማግኘት የ C ++ ኮድ

#include <iostream>
using namespace std;
#define MAX 100

int PreProductArray[MAX];
int PreInverseProduct[MAX];

int InverseP(int a, int modulo)
{
    int mP = modulo, temp, quotient;
    int xP = 0, x = 1;

    if (modulo == 1)
        return 0;

    while (a > 1)
    {
        quotient = a / modulo;

        temp = modulo;

        modulo = a % modulo;
        a = temp;

        temp = xP;

        xP = x - quotient * xP;

        x = temp;
    }
    if (x < 0)
        x += mP;

    return x;
}

void calculatePreProduct(int A[], int N, int P)
{
    PreProductArray[0] = A[0];

    for (int i = 1; i < N; i++)
    {
        PreProductArray[i] = PreProductArray[i - 1] *A[i];

        PreProductArray[i] = PreProductArray[i] % P;
    }
}
void calculatePreInverseProduct(int A[], int N, int P)
{
    PreInverseProduct[0] = InverseP(PreProductArray[0], P);

    for (int i = 1; i < N; i++)
        PreInverseProduct[i] = InverseP(PreProductArray[i], P);
}
int calculateProduct(int A[], int L, int R, int P)
{
    L = L - 1;
    R = R - 1;
    int ans;

    if (L == 0)
        ans = PreProductArray[R];
    else
        ans = PreProductArray[R] *
              PreInverseProduct[L - 1];

    return ans;
}

int main()
{
    int Arr[] = { 1, 2, 3, 4, 5, 6 };

    int N = sizeof(Arr) / sizeof(Arr[0]);

    int Modulo = 131;
    calculatePreProduct(Arr, N, Modulo);
    calculatePreInverseProduct(Arr, N, Modulo);

    int Left = 1, Right = 6;
    cout << calculateProduct(Arr, Left, Right, Modulo) << endl;

    Left = 2, Right = 4;
    cout << calculateProduct(Arr, Left, Right, Modulo)
         << endl;
    return 0;
}
65
24

በአንድ ረድፍ ውስጥ የክልሎችን ምርቶች ለማግኘት የጃቫ ኮድ

class ProductInRange
{

    static int MAX = 100;
    static int PreProductArray[] = new int[MAX];
    static int PreInverseProduct[] = new int[MAX];

    static int InverseP(int a, int modulo)
    {
        int mP = modulo, temp, quotient;
        int xP = 0, x = 1;

        if (modulo == 1)
            return 0;

        while (a > 1)
        {
            quotient = a / modulo;

            temp = modulo;

            modulo = a % modulo;
            a = temp;

            temp = xP;

            xP = x - quotient * xP;

            x = temp;
        }
        if (x < 0)
            x += mP;

        return x;
    }
    
    static void calculatePreProduct(int A[], int N, int P)
    {
        PreProductArray[0] = A[0];

        for (int i = 1; i < N; i++)
        {
            PreProductArray[i] = PreProductArray[i - 1] *
                                 A[i];
            PreProductArray[i] = PreProductArray[i] % P;
        }
    }
    
    static void calculatePreInverseProduct(int A[], int N, int P)
    {
        PreInverseProduct[0] = InverseP(PreProductArray[0], P);

        for (int i = 1; i < N; i++)
            PreInverseProduct[i] = InverseP(PreProductArray[i],
                                            P);
    }
    
    static int calculateProduct(int A[], int L, int R, int P)
    {
        L = L - 1;
        R = R - 1;
        int ans;

        if (L == 0)
            ans = PreProductArray[R];
        else
            ans = PreProductArray[R] *
                  PreInverseProduct[L - 1];

        return ans;
    }
    
    public static void main(String[] args)
    {

        int Arr[] = { 1, 2, 3, 4, 5, 6 };

        int Modulo = 131;
        calculatePreProduct(Arr, Arr.length, Modulo);
        calculatePreInverseProduct(Arr, Arr.length,
                                   Modulo);
        int Left = 1, Right = 6;
        System.out.println(calculateProduct(Arr, Left,
                                            Right, Modulo));
        Left = 2;
        Right = 4;
        System.out.println(calculateProduct(Arr, Left,
                                            Right, Modulo));

    }
}
65
24

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (N log M + Q) ፣ እዚህ መዝገብ M ለምርት ተቃራኒውን በማግኘቱ ነው ፡፡ እና ከዚያ ለጥያቄዎች መልስ ኦ (ጥ)።

የቦታ ውስብስብነት

ኦ (ኤን) የት "N" በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። ምክንያቱም እኛ አከማችተናል ቅድመ ምርትቅድመ ምርት ድርድሮች