6506: BZOJ2506:calc

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

           给一个长度为n的非负整数序列A1,A2,…,An。现有m个询问,每次询问给出l,r,p,k,问满足l<=i<=r且Ai mod p = k的值i的个数。


输入格式

         第一行两个正整数n和m。          第二行n个数,表示A1,A2,…,An。          以下m行,每行四个数分别表示l,r,p,k。满足1<=l<=r<=n。  


输出格式

         对于每个询问,输出一行,表示可行值i的个数。  


样例输入

         5 2
         1 5 2 3 7
         1 3 2 1
         2 5 3 0
 

样例输出

         2
        1 

提示

数据范围:
         0<n,m<=10^5,任意1<=i<=n满足Ai<=10^4,0<p<=10^4,0<=k<p。


题目来源

2011福建集训

加入题单

上一题 下一题 算法标签: