0

我有一个来自互联网的问题，我有一个 N 个整数的数组，并且必须在给定数组的左（L）和右段（R）的情况下执行段乘法一些 T 次，并以给定的模数（M）为模返回答案.

约束

N,T<=100000

1<=L<=R<=N

M<=10^9

和整数 <=100

前任-

输入

5(N) 2 5 8 9 4 4(T) 1 2 3 2 3 4 1 1 1 1 5 100000

输出

1 0 0 2880

所以我已经解决了这个问题，但它有点慢我需要提示来优化我的程序。

#include "stdio.h"

int main(void)
{
        int t;
        scanf("%d",&t);

        int Array[t+1];


    for (int i = 1; i <=t; i++)
    {
        scanf("%d",&Array[i]);
    }

    int N;
    scanf("%d",&N);


    for (int i = 0; i <N ; i++)
    {

        long long a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        long long Product = 1;
        if (c==1)
        {
            Product = 0;

        }
        else
        {

            for (int j = a; j <=b ; j++)
            {

                Product *= Array[j];

                if (Product>=10000000000000000)
                {
                    Product%=c;
                }
            }

        }

        Product%=c;


        printf("%lld\n",Product );

    }

    return 0;
}
4

1 回答 1

2

提示

您可以为每个小于 100 的素数 p 计算一个数组 A_p[i]，它记录了 p 将数组的第 i^th 个条目除以多少次。

然后你可以计算一个二级数​​组 B_p[j]，它是 A_p[i] 的累积和，对于 i 直到并包括 j。（这可以通过递归 B_p[i]=B_p[i-1]+A_p[i] 在 O(n) 中完成。）

这个辅助数组将允许您计算任何范围内每个素数的总功率。例如，如果您想知道素数 5 在数组条目 10 到 100 中出现的次数，您可以计算 B_5[100]-B_5[10-1]。

因此，对于每个查询，您可以通过将每个素数提高到相应的幂并将结果相乘以 M 为模来计算最终答案。请注意，有一种称为平方求幂的技术可以提高计算效率。

如果 0 是可能的整数，则将 0 添加到计算中考虑的素数列表中。

出于兴趣

请注意，这种使用累积和的方法在许多情况下都非常有用。例如，用于人脸识别的 Viola-Jones 方法在 2 维中使用该技术的一个版本，以便能够有效地计算 2d 过滤器。

于 2013-08-07T21:27:14.237 回答