当前位置: 首页 > news >正文

济南招聘网武汉seo公司

济南招聘网,武汉seo公司,做营销网站seo,青岛建站开发文章目录 题目描述输入格式输出格式输入输出样例 #1输入 #1输出 #1 输入输出样例 #2输入 #2输出 #2 提交链接提示解析参考代码 题目描述 小杨认为,所有大于等于 a a a 的完全平方数都是他的超级幸运数。 小杨还认为,所有超级幸运数的倍数都是他的幸运…

文章目录

  • 题目描述
  • 输入格式
  • 输出格式
  • 输入输出样例 #1
    • 输入 #1
    • 输出 #1
  • 输入输出样例 #2
    • 输入 #2
    • 输出 #2
  • 提交链接
  • 提示
  • 解析
  • 参考代码

题目描述

小杨认为,所有大于等于 a a a 的完全平方数都是他的超级幸运数。

小杨还认为,所有超级幸运数的倍数都是他的幸运数。自然地,小杨的所有超级幸运数也都是幸运数。

对于一个非幸运数,小杨规定,可以将它一直 + 1 +1 +1,直到它变成一个幸运数。我们把这个过程叫做幸运化。例如,如果 a = 4 a=4 a=4,那么 4 4 4 是最小的幸运数,而 1 1 1 不是,但我们可以连续对 1 1 1 3 3 3 + 1 +1 +1 操作,使其变为 4 4 4,所以我们可以说, 1 1 1幸运化后的结果是 4 4 4

现在,小杨给出 N N N 个数,请你首先判断它们是不是幸运数;接着,对于非幸运数,请你将它们幸运化。

输入格式

第一行 2 2 2 个正整数 a , N a, N a,N

接下来 N N N 行,每行一个正整数 x x x ,表示需要判断(幸运化)的数。

输出格式

输出 N N N 行,对于每个给定的 x x x ,如果它是幸运数,请输出 lucky,否则请输出将其幸运化后的结果。

输入输出样例 #1

输入 #1

2 4 
1 
4 
5 
9

输出 #1

4 
lucky 
8 
lucky

输入输出样例 #2

输入 #2

16 11 
1 
2 
4 
8 
16 
32 
64 
128 
256 
512
1024

输出 #2

16 
16 
16 
16 
lucky 
lucky 
lucky 
lucky 
lucky 
lucky 
lucky

提交链接

平均分配

提示

样例解释 1

虽然是完全平方数,但它小于 a a a,因此它并不是超级幸运数,也不是幸运数。将其进行 3 3 3 + 1 +1 +1 操作后,最终得到幸运数 4 4 4。4是幸运数,因此直接输出 lucky

5 5 5 不是幸运数,将其进行 3 3 3 + 1 +1 +1 操作后,最终得到幸运数 8 8 8

9 9 9 是幸运数,因此直接输出 lucky

数据规模

对于 30 % 30\% 30% 的测试点,保证 a , x ≤ 100 , N ≤ 100 a,x \le 100,N \le 100 a,x100,N100

对于 60 % 60\% 60% 的测试点,保证 a , x ≤ 1 0 6 a,x \le 10^6 a,x106

对于所有测试点,保证 a ≤ 1 , 000 , 000 a \le 1,000,000 a1,000,000;保证 N ≤ 2 × 1 0 5 N \le 2 \times 10^5 N2×105;保证 1 ≤ x ≤ 1 , 000 , 001 1 \le x \le 1,000,001 1x1,000,001

解析

此题的关键,找出:

  1. 找出所有超级幸运数:即大于等于 a a a 的完全平方数;

  2. 找出所有幸运数:所有超级幸运数及它们的倍数。

先考虑 30 % 30\% 30% 的数据。

此时的 a a a x x x 的最大范围为 100 100 100。我们可以暴力枚举一定范围,把这个范围内的完全平方数全部找到。 a ∼ 1000 a \sim 1000 a1000 这个范围一定是完全足够。

v i s [ ] vis[] vis[] 来标记幸运数
枚举完全平方数及其倍数

//判断一个数 是否为完全平方数
bool check(int x)
{int ave = sqrt(x);return ave * ave == x;
}vector<int>ans;  //存储 1e3 范围内的幸运数字
//只考虑1e3的数据 看能过多少测试点
for(int i = a; i <= Mx; i++)
{if(check(i)){if(!vis[i]){ans.push_back(i);vis[i] = true;//考虑1e3范围内的超级幸运数的倍数int rate = 2;while(rate * i <= Mx)  //考虑超级幸运数的倍数 {if(!vis[rate * i]){ans.push_back(rate * i);vis[rate * i] = true;}rate++;}}}
}

对于输入的 n n n 个数 x x x。若被标记则输出lucky,否则我们可以根据二分找到第一个大于 x x x 的位置输出。

sort(ans.begin() , ans.end());  //从小到大排序
for(int i = 1; i <= n; i++)
{if(vis[x[i]])cout << "lucky" << endl;else{int pos = upper_bound(ans.begin() , ans.end() , x[i]) - ans.begin();cout << ans[pos] << endl;}}

对于 100 % 100\% 100% 的数据。
a ≤ 1 , 000 , 000 a \le 1,000,000 a1,000,000 1 ≤ x ≤ 1 , 000 , 001 1 \le x \le 1,000,001 1x1,000,001

最极端的情况, x x x 1000001 1000001 1000001 a a a 1000000 1000000 1000000,若没有倍数的情况,大于 a a a 的最小的完全平方数为 1002001 1002001 1002001

我们可以借助 30 % 30\% 30% 数据的思路,对代码进行优化,分析时间复杂度。

平方数从 s q r t ( a ) sqrt(a) sqrt(a) 开始,最大的范围到 1002001 ( 1001 ∗ 1001 = 1002001 ) 1002001(1001 * 1001 = 1002001) 1002001(10011001=1002001)

for (int i = ceil(sqrt(a)); i <= 1001; i++)

对于每一个完全平方数我们依然选出其倍数进行存储。

// 能得出当x=1000001 最差的幸运数为1002001,1002001为完全平方数
for (int i = ceil(sqrt(a)); i <= 1001; i++)
{int x = i * i; // x为完全平方数for (int j = 1; j * x <= 1002001; j++){if (!vis[x * j])   //超级幸运数的倍数{ans.push_back(x * j);vis[x * j] = true;}}
}

此题的难点在于分析时间复杂度,考虑上述预处理代码的时间复杂度:

遍历从 a a a u p = 1002001 up = 1002001 up=1002001

  • 如果 i i i 是完全平方数,就遍历它的所有倍数 j = i , 2 i , 3 i , . . . , u p j = i, 2i, 3i, ..., up j=i,2i,3i,...,up,时间为 O ( u p / i ) O(up / i) O(up/i)

一共操作的次数: ∑ i 2 ≥ a u p u p i 2 \sum_{i^2≥a}^{\sqrt{up}} \frac{up}{i^2} i2aup i2up

化简后,求和为一个收敛常数,时间复杂度大约为 1 e 6 1e6 1e6 级别。

预处理后,对于每一个数 判断标记 + 二分 进行输出。

参考代码

#include <bits/stdc++.h>
using namespace std;bool vis[1100000];int main()
{int a, n;cin >> a >> n;vector<int> ans; // 存储幸运数字// 能得出当x=1000001 最差的幸运数为1002001,1002001为完全平方数for (int i = ceil(sqrt(a)); i <= 1001; i++){int x = i * i; // x为完全平方数for (int j = 1; j * x <= 1002001; j++){if (!vis[x * j])   //超级幸运数的倍数{ans.push_back(x * j);vis[x * j] = true;}}}sort(ans.begin() , ans.end());while (n--){int x;cin >> x;if (vis[x])cout << "lucky" << endl;else{int pos = upper_bound(ans.begin(), ans.end(), x) - ans.begin();cout << ans[pos] << endl;}}return 0;
}
http://www.cadmedia.cn/news/2190.html

相关文章:

  • 网络舆情应急预案求好用的seo软件
  • 高校网站建设申请怎么写天津seo优化公司哪家好
  • 提供网站建设案例百度怎么投放广告
  • 互联网App网站建设方案推广的公司
  • 动漫制作专业可以升大专吗厦门网站seo
  • 网站找哪家做较好百度关键词关键词大全
  • 政府网站模板下载整合营销传播的定义
  • 佛山企业快速建站广州网站优化推广
  • 沈阳大型网站建设卡点视频免费制作软件
  • 网站怎么做留言提交功能淘宝指数查询
  • 网站开发趋势好看的web网页
  • 设计网页页面优化大师下载安装免费
  • 苏州网站推广949公社招聘信息
  • 高清免费爱做网站河南郑州网站推广优化外包
  • 网站建设中 翻译怎么提高seo关键词排名
  • 太湖县住房和城乡建设网站市建设局点击seo软件
  • 建设网站图片大全电商网站设计
  • 南京多样化的网站建设定制公司重庆森林台词
  • 集团网站建设行业现状浏览器谷歌手机版下载
  • 制作网站可以赚钱吗免费打广告网站
  • 盐山网站建设如何在网上推广自己的产品
  • 曲阜网架公司网站优化 福州
  • 公司网站建设需求书seo的工作原理
  • 都昌网站建设新闻近期大事件
  • 贵州省安顺市网站建设广告网站推荐
  • 遵义做企业网站facebook海外推广
  • 找人做淘宝网站国外免费网站建设
  • 商业网站建设目标seo在线短视频发布页
  • 卓商网站建设公司网络推广方式有哪些
  • 房地产开发公司网站建设方案模板网站查询地址