Luogu1574 超级数

时间:2022-09-04 22:45:14

Luogu1574 超级数

\(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 超级数的更多相关文章

  1. UVa 10624 - Super Number

    题目大意 给定两个数n和m,如果长度为m的数满足对于每个i(n<=i<=m),数字的前i位都能被i整除,那么这个数就是超级数,求出字典序最小的符合要求的超级数. 分析 直接暴力搜索 #in ...

  2. &lbrack;kuangbin带你飞&rsqb;专题十四 数论基础

            ID Origin Title   111 / 423 Problem A LightOJ 1370 Bi-shoe and Phi-shoe   21 / 74 Problem B ...

  3. UVA11752 The Super Powers —— 数论、枚举技巧

    题目链接:https://vjudge.net/problem/UVA-11752 题意: 一个超级数是能够至少能表示为两个数的幂,求1~2^64-1内的超级数. 题解: 1.可知对于 n = a^b ...

  4. MySQL使用pt-online-change-schema工具在线修改1&period;6亿级数据表结构

    摘  要:本文阐述了MySQL DDL 的问题现状.pt-online-schema-change的工作原理,并实际利用pt-online-schema-change工具在线修改生产环境下1.6亿级数 ...

  5. 精选10款超酷的HTML5&sol;CSS3菜单

    今天向大家精选了10款超酷的HTML5/CSS3菜单,给你的网页添加不一样的精彩,一起来围观一下吧. 1.CSS3手风琴菜单 下拉展开带弹性动画 利用CSS3技术可以实现各种各样的网页菜单,我们之前也 ...

  6. 不停机不停服务,MYSQL可以这样修改亿级数据表结构

    摘  要:本文阐述了MySQL DDL 的问题现状.pt-online-schema-change的工作原理,并实际利用pt-online-schema-change工具在线修改生产环境下1.6亿级数 ...

  7. 完全用nosql轻松打造千万级数据量的微博系统(转)

    原文:http://www.cnblogs.com/imxiu/p/3505213.html 其实微博是一个结构相对简单,但数据量却是很庞大的一种产品.标题所说的是千万级数据量 也并不是一千万条微博信 ...

  8. 完全用nosql轻松打造千万级数据量的微博系统

    其实微博是一个结构相对简单,但数据量却是很庞大的一种产品.标题所说的是千万级数据量也并不是一千万条微博信息而已,而是千万级订阅关系之间发布.在看 我这篇文章之前,大多数人都看过sina的杨卫华大牛的微 ...

  9. 字节跳动基于Apache Hudi构建EB级数据湖实践

    来自字节跳动的管梓越同学一篇关于Apache Hudi在字节跳动推荐系统中EB级数据量实践的分享. 接下来将分为场景需求.设计选型.功能支持.性能调优.未来展望五部分介绍Hudi在字节跳动推荐系统中的 ...

随机推荐

  1. YARN资源调度器

    YARN资源调度器 转载请注明出处:http://www.cnblogs.com/BYRans/ 概述 集群资源是非常有限的,在多用户.多任务环境下,需要有一个协调者,来保证在有限资源或业务约束下有序 ...

  2. 循序渐进Python3(八) -- 0 -- 初识socket

    socket通常也称作"套接字",用于描述IP地址和端口,是一个通信链的句柄,应用程序通常通过"套接字"向网络发出请求或者应答网络请求. socket起源于Un ...

  3. leetcode Largest Rectangle in Histogram 解法二

    上一篇文章讲了该题的一个解法.后来又发现一个更好的解法. 首先依旧考虑一个升序的数列,例如1,2,3,4,5.那么它的最大矩形显然是有5种可能,即 1*5,2*4,3*3,4*2,1*5.所以最大的矩 ...

  4. IOS某个ViewController禁止自动旋转

    IOS屏幕自动旋转,强制横竖屏方法: - (BOOL)shouldAutorotate { return YES; } - (NSUInteger)supportedInterfaceOrientat ...

  5. ORACLE JOB创建

    Connected Connected as focususer SQL> SQL> --JOB 需要在命令行执行: SQL> --抽数job SQL> CREATE OR R ...

  6. 海康&sol;大华 IpCamera RTSP地址和格式

    海康:rtsp://[username]:[password]@[ip]:[port]/[codec]/[channel]/[subtype]/av_stream说明:username: 用户名.例如 ...

  7. maven3自定义archetype

    maven使用起来还是很方便,但默认自带的archetype配置junit版本比较老.每次创建新项目都要手动修改junit版本,所以就想着能不能自己建一个新版本出来,省得每次手动修改的麻烦. 网上找了 ...

  8. 「译」图解 ArrayBuffers 和 SharedArrayBuffers

    作者:Lin Clark 译者:Cody Chan 原帖链接:A cartoon intro to ArrayBuffers and SharedArrayBuffers 这是图解 SharedArr ...

  9. java 爬坑记-&commat;WebServlet异步 不支持&commat;Autowired

    上篇文章解决了500那个错误, 程序能接受到request ,进行到调用service 服务时,提示线程空指针异常, 检查发现 //@Autowired //OpHistoryService ophi ...

  10. 潭州课堂25班:Ph201805201 爬虫高级 第二课 sclapy 框架 &lpar;课堂笔记)

    win 下安装 sclapy 先安装 pip install wheel py 库下载地址:https://www.lfd.uci.edu/~gohlke/pythonlibs/#twisted 在这 ...