程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CF：358C 暴力DP篩選素數預處理

CF：358C 暴力DP篩選素數預處理

編輯：C++入門知識

C. Bear and Prime Numbers time limit per test 2 seconds memory limit per test 512 megabytes input standard input output standard output

Recently, the bear started studying data structures and faced the following problem.

You are given a sequence of integers x1,?x2,?...,?xn of length n and m queries, each of them is characterized by two integers li,?ri. Let's introduce f(p) to represent the number of such indexes k, that xk is divisible by p. The answer to the query li,?ri is the sum: $\$ , where S(li,?ri) is a set of prime numbers from segment [li,?ri] (both borders are included in the segment).<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+CkhlbHAgdGhlIGJlYXIgY29wZSB3aXRoIHRoZSBwcm9ibGVtLjwvcD4KCgoKSW5wdXQKPHA+ClRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGludGVnZXIgPGVtPm48L2VtPiAoMT+h3D88ZW0+bjwvZW0+P6HcPzEwNikuCiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgPGVtPm48L2VtPiBpbnRlZ2VycyA8ZW0+eDwvZW0+MSw/PGVtPng8L2VtPjIsPy4uLiw/PGVtPng8L2VtPjxlbT5uPC9lbT4gKDI/odw/PGVtPng8L2VtPjxlbT5pPC9lbT4/odw/MTA3KS4KIFRoZSBudW1iZXJzIGFyZSBub3QgbmVjZXNzYXJpbHkgZGlzdGluY3QuPC9wPgo8cD4KVGhlIHRoaXJkIGxpbmUgY29udGFpbnMgaW50ZWdlciA8ZW0+bTwvZW0+ICgxP6HcPzxlbT5tPC9lbT4/odw/NTAwMDApLgogRWFjaCBvZiB0aGUgZm9sbG93aW5nIDxlbT5tPC9lbT4gbGluZXMgY29udGFpbnMgYSBwYWlyIG9mIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycywgPGVtPmw8L2VtPjxlbT5pPC9lbT4gYW5kIDxlbT5yPC9lbT48ZW0+aTwvZW0+KDI/odw/PGVtPmw8L2VtPjxlbT5pPC9lbT4/odw/PGVtPnI8L2VtPjxlbT5pPC9lbT4/odw/MqGkMTA5KSChqgogdGhlIG51bWJlcnMgdGhhdCBjaGFyYWN0ZXJpemUgdGhlIGN1cnJlbnQgcXVlcnkuPC9wPgoKCgpPdXRwdXQKPHA+ClByaW50IDxlbT5tPC9lbT4gaW50ZWdlcnMgoaogdGhlIGFuc3dlcnMgdG8gdGhlIHF1ZXJpZXMgb24gdGhlIG9yZGVyIHRoZSBxdWVyaWVzIGFwcGVhciBpbiB0aGUgaW5wdXQuPC9wPgoKCgpTYW1wbGUgdGVzdChzKQoKCgppbnB1dAo8cHJlIGNsYXNzPQ=="brush:java;">6 5 5 7 10 14 15 3 2 11 3 12 4 4 output

9
7
0

input

7
2 3 5 7 11 4 8
2
8 10
2 123

output

0
7

Note

Consider the first sample. Overall, the first sample has 3 queries.

The first query l?=?2, r?=?11 comes. You need to count f(2)?+?f(3)?+?f(5)?+?f(7)?+?f(11)?=?2?+?1?+?4?+?2?+?0?=?9.
The second query comes l?=?3, r?=?12. You need to count f(3)?+?f(5)?+?f(7)?+?f(11)?=?1?+?4?+?2?+?0?=?7.

The third query comes l?=?4, r?=?4. As this interval has no prime numbers, then the sum equals 0.

這題太神了！比賽的時候不知道怎麼做，唉……沒想到可以這樣暴力的。太神了……遞推的DP，查詢時間復雜為O(1)，比線段樹還快，這個能這樣暴力真是服了，見識短淺啊……

dp[i]表示當前2到 i 這中間能被那n 個數整除的數之和……然後求 l 到 r 的時候就可以直接dp [ r ] - dp [ l-1] 了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 10000005
#define MN 3005
#define INF 10000007
#define eps 1e-7
using namespace std;
typedef long long ll;
int vis[MM],dp[MM],is[MM];
void getprime()
{
    int i,j;
    for(i=2;i<=MM;i++)
        if(!is[i])
        {
            if(vis[i]) dp[i]+=vis[i];
            for(j=i+i;j<=MM;j+=i)
            {
                if(vis[j]) dp[i]+=vis[j];
                is[j]=1;
            }
        }
    for(i=2;i<=MM;i++)
        dp[i]+=dp[i-1];
}
int main()
{
    int n,m,i,a,l,r;
    sca(n);
    for(i=0;iMM?MM:l;
        r=r>MM?MM:r;
        pri(dp[r]-dp[l-1]);
    }
    return 0;
}