当前位置：首页 -> AI编程基础 -> c++编程基础

CF：Problem 385C - Bear and Prime Numbers 预处理DP

2014-11-24 09:23:36 · 作者: · 浏览: 2
标签: Problem 385C Bear and Prime Numbers 处理
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.2cto.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.

  1. 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.
  2. 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.
  3. The third query comes l = 4, r = 4. As this interval has no prime numbers, then the sum equals 0.
    题意：题意比赛的时候竟然没看懂！！！给出n个数，然后给出l与r，然后求出 l 到 r 中是素数且在这n个数中有多少个数可以整除l到r 中是素数的数。 思路：输入这n个数的时候统计数出现多少次（即c[x]++）；然后用打表的方法求出每个素数被哪些数整除了的次数（即dp[i]+=d[j],非素数置-1）；然后连加滚动数组到最后，即： dp[i]=(dp[i]<0 0:dp[i])+dp[i-1]; 意思就是当前数等于前一个数的次数加上当前数的次数（如果当前数是非素数，则置0）。 然后输入l,r,就可以直接输出 dp[r]-dp[l-1],因为已经预处理过dp[i]了嘛！相减其实就是等于dp[l]到dp[r]之间的素数被整除的次数相加。因为非素数为0，所以相减是无影响的，非素数的次数会等于前一个最接近的素数的次数，由滚动数组状态方程可以看出。 感觉：本来刚开始的想法就是先判断出素数再一个一个判断，但是确实数太大会超时。所以只能是DP了。但是木想到暴力可以这样解决，太强暴了！！！受益匪浅啊！多上上CF决对有益处！！！而且这段时间我也想把DP想法与状态方法的求解有更大的提高，DP真是只要能想到，决对没有做不出来的，太爽了。算法的力量太强暴了！！！！！！！！！！！ 
    #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 f(i,a,n) for(i=a;i
                  
                   =0) { dp[i]=c[i]; for(j=i+i; j
                   
                    =MM) r=MM-2; l>r puts("0"):pri(dp[r]-dp[l-1]); } return 0; }