2018 CCPC 女生赛 hdoj6287 口算训练

妖狐艹你老母 2021-11-26 20:36 218阅读 0赞

题目地址：[http://acm.hdu.edu.cn/showproblem.php?pid=6287][http_acm.hdu.edu.cn_showproblem.php_pid_6287]

Summarize:

1、分解质因数；

2、二分查找函数lower\_bound与upper\_bound；

3、注意输入输出超时与初始化；

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    const int N = 1e5+5;
    int T, n, m;
    vector<int> prime[N];
    
    int query(int x, int l, int r)
    {
    	return upper_bound(prime[x].begin(), prime[x].end(), r) - lower_bound(prime[x].begin(), prime[x].end(), l);
    }
    
    bool half_find(int l ,int r, int k)
    {
    	for(int i=2; i*i<=k; i++) {
    		int cnt=0;
    		while(!(k%i)) {
    			k /= i;
    			cnt++;
    		}
    		if(cnt > query(i, l, r)) return false;
    	}
    	if(k>1 && query(k, l, r)<1) return false;
    	return true;
    }
    
    int main()
    {
    	scanf("%d", &T);
    	while(T--)
    	{
    		for(int i=1; i<N; i++)
    			prime[i].clear();
    		scanf("%d%d", &n ,&m);
    		for(int i=1, x; i<=n; i++) {
    			scanf("%d", &x);
    			for(int j=2; j*j<=x; j++) {
    				while(!(x%j)) {
    					x /= j;
    					prime[j].push_back(i);
    				}
    			}
    			if(x>1) prime[x].push_back(i);
    		}
    		
    		for(int i=0,l,r,d; i<m; i++) {
    			scanf("%d%d%d", &l, &r, &d);
    			if(!half_find(l, r, d))
    				printf("No\n");
    			else printf("Yes\n");
    		}
    	}
    	
    	return 0;
    }

转载于:https://www.cnblogs.com/liubilan/p/10940300.html

[http_acm.hdu.edu.cn_showproblem.php_pid_6287]: http://acm.hdu.edu.cn/showproblem.php?pid=6287

发表评论取消回复

表情：

评论列表（有 0 条评论，218人围观）

还没有评论，来说两句吧...

相关阅读

相关【状压DP】2021ccpc女生赛 C 连锁商店

[Problem - C - Codeforces][] 题意： ![114e591cb2614aeaaa4c482dd11f9021.png][] 思路：一开始想的

深藏阁楼爱情的钟/ 2024年03月17日 09:25/ 0 赞/ 56 阅读

相关 2018ICPC 沈阳训练赛

C.1:33:41(-1) solved by zcz 推式子找规律 ![ContractedBlock.gif][] ![ExpandedBlockStart.g

Dear 丶/ 2023年10月11日 13:27/ 0 赞/ 51 阅读

相关 2018ICPC 焦作训练赛

赛后总结: 先把所有的可做题放上线程，debug在线程上有题的时候永远下机找宁愿机下多线程debug不要机下多线程空想题 A. 0:05:54 solved by

刺骨的言语ヽ痛彻心扉/ 2023年10月11日 13:27/ 0 赞/ 48 阅读

相关 2018ICPC 南京训练赛

赛后总结： 1.补字符串 2.前期交题看三遍 3.认真听取zcz兄弟的意见最后时间该冲的时候就要冲 A.分情况讨论一下 K > 2先手必胜 N可能是0 so

桃扇骨/ 2023年10月11日 13:27/ 0 赞/ 60 阅读

相关 2018CCPC吉林训练赛题解

A. 00:09:13 solved by hl 打个表发现规律是3个odd,5个even,7个odd,9个even....... 很显然是个等差数列，二分判断项

ゝ一世哀愁。/ 2023年10月11日 13:26/ 0 赞/ 49 阅读

相关 2019 CCPC网络赛

一到网络赛，大家都是东亚之光 1001 00:23:46 solved by hl 签到枚举一下位就行了 ![ContractedBlock.gif][]

左手的ㄟ右手/ 2023年10月10日 07:49/ 0 赞/ 72 阅读

相关 CCPC2019网络赛

1001：输出A&B 特判A&B=0 1007: 思路：按照题意去写，分为四个部分，只有第三部分与第一部分相反，其余都与第一部分相同所以我们以第一部分为基准，去扩

深藏阁楼爱情的钟/ 2023年08月17日 16:26/ 0 赞/ 136 阅读

相关 2018 CCPC 女生赛 hdoj6287 口算训练

题目地址：[http://acm.hdu.edu.cn/showproblem.php?pid=6287][http_acm.hdu.edu.cn_showproblem.ph

妖狐艹你老母/ 2021年11月26日 20:36/ 0 赞/ 219 阅读

相关 2018 CCPC 桂林站（upc复现赛）总结

　　比赛一开始盯上了A题和G题，一个小时过去了还没有出题，心里有些乱。这时我看D题很多人过了，于是宝儿去看D题，说D题简单，转化成二进制暴力，于是就去做了。写的时候好像思路有点

痛定思痛。/ 2021年11月19日 15:22/ 0 赞/ 307 阅读

相关 HDU6287 ／BZOJ 5358 口算训练

[传送门][Link 1] 题解：由唯一分解可以知道每个数都能表示成素数的乘积，因此我们只要判断\[l,r\]区间内是否出现过d分解成素数后各个素数的次数。用主席树维护之前l

爱被打了一巴掌/ 2021年09月20日 11:40/ 0 赞/ 174 阅读