Codeforces Round #471 (Div. 2) C. Sad powers
2024-08-22 11:58:02
首先可以前缀和 ans = solve(R) - solve(L-1)
对于solve(x) 1-x当中符合条件的数
分两种情况
- 3,5,7,9次方的数，注意这地方不能含有平方次
- 平方数
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
std::vector<long long> oddNumber;
bool isSqaure(long long x) {
long long t1 = sqrt(x);
return t1 * t1 == x;
}
void pre() {
// get the a^p (p = 3,5,7,9)
oddNumber.clear();
for (long long i = 2; i < 1000001; ++i) {
if (!isSqaure(i)) {
long long initNumber = i * i * i;
long long multiplyNumber = i * i;
oddNumber.push_back(initNumber);
while (1.0 * initNumber * multiplyNumber <= 1e18) {
initNumber *= multiplyNumber;
oddNumber.push_back(initNumber);
}
}
}
sort(oddNumber.begin(), oddNumber.end());
oddNumber.erase(unique(oddNumber.begin(), oddNumber.end()), oddNumber.end());
}
long long solve(long long number) {
if (number == 0)
return 0;
long long result = upper_bound(oddNumber.begin(), oddNumber.end(), number) - oddNumber.begin();
result += (long long)sqrt(number);
return result;
}
int main() {
int Q;
pre();
while (~scanf("%d", &Q)) {
for (int i = 0; i < Q; ++i) {
long long L, R;
scanf("%lld %lld", &L, &R);
printf("%lld\n", solve(R) - solve(L - 1));
}
}
return 0;
}
最新文章
- 用CIL写程序:从“call vs callvirt”看方法调用
- Docker 基础命令 简要入门
- linux 命令行模式下，浏览网页
- git的初步使用
- 使用CXF发布WebService服务简单实例
- Cocos2d-x——CocosBuilder官方帮助文档翻译3 动画
- OpenSessionInViewFilter 的配置及替代方案（转）
- 学习面试题Day03
- VMware Workstation 12 Pro 之安装林耐斯Debian X64系统
- Android线上Bug热修复分析
- 获取手机当前显示的ViewController
- iptables防火墙详解（二）
- 域名到站点的负载均衡技术一览（主要是探讨一台Nginx抵御大并发的解决方案）（转）https://www.cnblogs.com/EasonJim/p/7823410.html
- c语言学习笔记-break
- redis的一命令
- [apr] Apache Portable Runtime
- python记录_day27 tcp/ip五层模型
- Python序列化-pickle和json模块
- QT-提示“database not open”
- 1550: Simple String （做得少的思维题，两个字符串能否组成另外一个字符串问题）