\(n\) 次询问不超过 \(a_i\) 的最大反素数
\(n\leq10^5,\ a_i\leq10^{17}\)
数论
似乎重题 bzoj1053 [HAOI2007]反素数ant ?然而跑不过此题
首先发现 \(10^{17}\) 以内的反素数数量很少,可以直接打表解决……
然而有更优美的解法
由于数量少,显然有很多反素数是被重复计算了的
考虑继承,从大往小跑,如果上一个答案小于当前询问,当前询问的答案即为上一个答案
这种方法跑的很快,因为最多只会算遍所有反素数
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int p[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
int n, tid[maxn];
ll now, res, val, Q[maxn], ans[maxn];
void dfs(int pos, ll sum, ll tot, int lst) {
for (ll i = 0, t = sum; i <= lst; i++, t *= p[pos]) {
if (pos < 16) dfs(pos + 1, t, tot * (i + 1), i);
if ((res >= t && val <= tot) || (res < t && val < tot)) {
res = t, val = tot;
}
if (t * p[pos] > now) break;
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", Q + i), tid[i] = i;
}
sort(tid + 1, tid + n + 1, [](int x, int y) {
return Q[x] > Q[y];
});
for (int i = 1; i <= n; i++) {
if (i > 1 && ans[tid[i - 1]] < Q[tid[i]]) {
ans[tid[i]] = ans[tid[i - 1]];
} else {
res = val = 1;
now = Q[tid[i]];
dfs(1, 1, 1, 1000);
ans[tid[i]] = res;
}
}
for (int i = 1; i <= n; i++) {
printf("%lld\n", ans[i]);
}
return 0;
}
Luogu1574 超级数的更多相关文章
-
UVa 10624 - Super Number
题目大意 给定两个数n和m,如果长度为m的数满足对于每个i(n<=i<=m),数字的前i位都能被i整除,那么这个数就是超级数,求出字典序最小的符合要求的超级数. 分析 直接暴力搜索 #in ...
-
[kuangbin带你飞]专题十四 数论基础
ID Origin Title 111 / 423 Problem A LightOJ 1370 Bi-shoe and Phi-shoe 21 / 74 Problem B ...
-
UVA11752 The Super Powers —— 数论、枚举技巧
题目链接:https://vjudge.net/problem/UVA-11752 题意: 一个超级数是能够至少能表示为两个数的幂,求1~2^64-1内的超级数. 题解: 1.可知对于 n = a^b ...
-
MySQL使用pt-online-change-schema工具在线修改1.6亿级数据表结构
摘 要:本文阐述了MySQL DDL 的问题现状.pt-online-schema-change的工作原理,并实际利用pt-online-schema-change工具在线修改生产环境下1.6亿级数 ...
-
精选10款超酷的HTML5/CSS3菜单
今天向大家精选了10款超酷的HTML5/CSS3菜单,给你的网页添加不一样的精彩,一起来围观一下吧. 1.CSS3手风琴菜单 下拉展开带弹性动画 利用CSS3技术可以实现各种各样的网页菜单,我们之前也 ...
-
不停机不停服务,MYSQL可以这样修改亿级数据表结构
摘 要:本文阐述了MySQL DDL 的问题现状.pt-online-schema-change的工作原理,并实际利用pt-online-schema-change工具在线修改生产环境下1.6亿级数 ...
-
完全用nosql轻松打造千万级数据量的微博系统(转)
原文:http://www.cnblogs.com/imxiu/p/3505213.html 其实微博是一个结构相对简单,但数据量却是很庞大的一种产品.标题所说的是千万级数据量 也并不是一千万条微博信 ...
-
完全用nosql轻松打造千万级数据量的微博系统
其实微博是一个结构相对简单,但数据量却是很庞大的一种产品.标题所说的是千万级数据量也并不是一千万条微博信息而已,而是千万级订阅关系之间发布.在看 我这篇文章之前,大多数人都看过sina的杨卫华大牛的微 ...
-
字节跳动基于Apache Hudi构建EB级数据湖实践
来自字节跳动的管梓越同学一篇关于Apache Hudi在字节跳动推荐系统中EB级数据量实践的分享. 接下来将分为场景需求.设计选型.功能支持.性能调优.未来展望五部分介绍Hudi在字节跳动推荐系统中的 ...
随机推荐
-
YARN资源调度器
YARN资源调度器 转载请注明出处:http://www.cnblogs.com/BYRans/ 概述 集群资源是非常有限的,在多用户.多任务环境下,需要有一个协调者,来保证在有限资源或业务约束下有序 ...
-
循序渐进Python3(八) -- 0 -- 初识socket
socket通常也称作"套接字",用于描述IP地址和端口,是一个通信链的句柄,应用程序通常通过"套接字"向网络发出请求或者应答网络请求. socket起源于Un ...
-
leetcode Largest Rectangle in Histogram 解法二
上一篇文章讲了该题的一个解法.后来又发现一个更好的解法. 首先依旧考虑一个升序的数列,例如1,2,3,4,5.那么它的最大矩形显然是有5种可能,即 1*5,2*4,3*3,4*2,1*5.所以最大的矩 ...
-
IOS某个ViewController禁止自动旋转
IOS屏幕自动旋转,强制横竖屏方法: - (BOOL)shouldAutorotate { return YES; } - (NSUInteger)supportedInterfaceOrientat ...
-
ORACLE JOB创建
Connected Connected as focususer SQL> SQL> --JOB 需要在命令行执行: SQL> --抽数job SQL> CREATE OR R ...
-
海康/大华 IpCamera RTSP地址和格式
海康:rtsp://[username]:[password]@[ip]:[port]/[codec]/[channel]/[subtype]/av_stream说明:username: 用户名.例如 ...
-
maven3自定义archetype
maven使用起来还是很方便,但默认自带的archetype配置junit版本比较老.每次创建新项目都要手动修改junit版本,所以就想着能不能自己建一个新版本出来,省得每次手动修改的麻烦. 网上找了 ...
-
「译」图解 ArrayBuffers 和 SharedArrayBuffers
作者:Lin Clark 译者:Cody Chan 原帖链接:A cartoon intro to ArrayBuffers and SharedArrayBuffers 这是图解 SharedArr ...
-
java 爬坑记-@WebServlet异步 不支持@Autowired
上篇文章解决了500那个错误, 程序能接受到request ,进行到调用service 服务时,提示线程空指针异常, 检查发现 //@Autowired //OpHistoryService ophi ...
-
潭州课堂25班:Ph201805201 爬虫高级 第二课 sclapy 框架 (课堂笔记)
win 下安装 sclapy 先安装 pip install wheel py 库下载地址:https://www.lfd.uci.edu/~gohlke/pythonlibs/#twisted 在这 ...