Gym 101102J---Divisible Numbers(反推技巧题)
2018-06-17 23:42:39来源:未知 阅读 ()
题目链接
http://codeforces.com/gym/101102/problem/J
Description
You are given an array A of integers of size N, and Q queries. For each query, you will be given a set of distinct integers S and two integers L and R that represent a range in the array. Your task is to count how many numbers in the given range are divisible by at least one number from the set.
Input
The first line of input contains a single integer T, the number of test cases.
The first line of each test case contains two integers, N and Q (1 ≤ N, Q ≤ 105), the size of the array and the number of queries, respectively.
The next line contains N space-separated integers, the values of the array A (1 ≤ Ai ≤ 109).
Each of the next Q lines contain the description of one query in the form:
LRS
Where L and R (1 ≤ L ≤ R ≤ N) represent the range, and S is an integer between 1 and 1023 (inclusive) and represents the set; consider the binary representation of the number S, if the ith bit (1-based) is 1, then the number i belongs to the set. Since S is less than1024, the values in the set are between 1 and 10.
For example: if S is equal to 6, the binary representation of 6 is 110, and this means the values in the set are 2 and 3.
The input was given in this way to reduce the size of the input file.
Output
Print the answer for each query on a single line.
Sample Input
1
4 2
2 5 3 8
1 3 2
2 4 355
1
3
题意:输入n,q表示由n个数构成的一个序列,q次询问,每次询问输入l r s s表示一个集合,s的二进制中的1的位置,如:6(10)=110(2) 对应集合{2,3} 现在求区间l~r中能被集合中的(任意一个)数整除的数的个数;
思路:因为s取值范围为1~1023 所以输入n个数时直接求出能被哪些s(对应的集合数)整除,然后用前缀和表示出来,那么每次查询时就是0(1)的了;
代码如下:
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> using namespace std; typedef long long LL; const int MAXN = 1e5+5; int sum[512][MAXN]; template <class T> inline void Scan(T &ret) { char c=getchar(); while(c<'0'||c>'9') c=getchar(); ret=c-'0'; while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); } int main() { int T; Scan(T); while(T--) { int n,q,x,s; Scan(n); Scan(q); ///memset(sum,0,sizeof(sum)); 加上超时!!! for(int i=1;i<=n;i++) { s=0; Scan(x); for(int j=2;j<=10;j++) if(x%j==0) s=s|(1<<(j-2)); for(int j=0;j<512;j++) sum[j][i]=sum[j][i-1]+((s&j)?1:0); } while(q--) { int l,r; Scan(l); Scan(r); Scan(x); if(x&1) printf("%d\n",r-l+1); else printf("%d\n",sum[x>>1][r]-sum[x>>1][l-1]); } } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 【题解】Building Strings Gym - 102152E 2020-03-31
- CodeForces Gym 100213F Counterfeit Money 2020-02-13
- Add Two Numbers 2019-08-16
- leetcode 136 Single Number bit Option 2019-08-16
- 2018-10-13 21:30:51 conversion of number systems 2018-10-14
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash