2018 CCPC 女生赛 hdoj6287 口算训练

妖狐艹你老母 2021-11-26 20:36 205阅读 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 条评论，205人围观）

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

相关阅读

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

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

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

相关 2018CCPC吉林训练赛题解

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

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

相关 CCPC2019网络赛

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

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

相关 2019ccpc省赛榜单

山东:[https://board.pintia.cn/][https_board.pintia.cn] 湖南:[https://ericxie.coding.me/201

Myth丶恋晨/ 2022年02月02日 17:53/ 0 赞/ 242 阅读

相关 CCPC2019吉林省赛&&东北地区赛游记

Preface 第一次打正式的线下赛三天，两场热身赛两场正赛，有点累 -------------------- Day 0 一大早从大学城叫滴滴去车站，差点迟到q

深藏阁楼爱情的钟/ 2021年12月13日 13:11/ 0 赞/ 305 阅读

相关 HDU重现赛之2019CCPC-江西省赛

本人蒟蒻，5个小时过了5道，看到好几个大佬AK，%%%%%%% [http://acm.hdu.edu.cn/contests/contest\_show.php?cid=8

谁借莪１个温暖的怀抱￠/ 2021年11月29日 22:30/ 0 赞/ 310 阅读

相关 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 赞/ 206 阅读

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

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

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

相关 HDU6287 ／BZOJ 5358 口算训练

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

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

相关 2018 CCPC网络赛1009 Tree and Permutation (HDU6446)(dfs or 树形dp)

Tree and Permutation Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536

谁践踏了优雅/ 2021年09月16日 05:10/ 0 赞/ 209 阅读