【ACM-ICPC 2018 南京赛区网络预赛 J】Sum
网络 2018 sum ACM 南京 赛区 ICPC
2023-09-14 09:03:44 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
线性筛求出每个数的最小质因子x for 从1-n 对于i,它的最小质因子为x 考虑i=a*b 如果i能被x^3整除 那么这x怎么分配给它的两个因子a,b都不行,(都有一个因子会分配至少2个以上,那么我们提出来一个x^2的话,a或b就能被x^2整除了)。所以ans[i] = 0 如果i能被x^2整除(先判断x^3再判断x^2这样能保证x就只能被x^2整除),那么ans[i] = ans[i/(x^2)] 因为这个x显然只能分到两边去(a,b各分配一个,不能都分配到a或都分配到b) 所以答案和i/(x^2)的一样.i/(x^2)有多少个答按a'*b',那么把a'和b'都各乘上x就ok 如果i只能被x整除 ans[i] = ans[i/x]*2 因为这个x有两种可能,分到a或者b。 所以i/x的每种方案a',b'。 加一个x乘在a'或者b'都能凑成i的方案.且乘1个x显然不会让它有平方因子。ans[1]=1
然后按照上面的规则递推就好
(再求个前缀和
【代码】
/*
N在const里面,可以改动;
求出2..N之间的所有质数;
放在zsb数组里面;
时间复杂度是O(N)的;
但是需要空间也是O(N)的;
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 2e7;
bool iszs[N + 10];
int mizs[N+10];
int ans[N+10];
vector <int> zsb;
int main() {
#ifdef LOCAL_DEFINE
freopen("rush_in.txt", "r", stdin);
#endif
memset(iszs, true, sizeof iszs);
for (int i = 2; i <= N; i++) {
if (iszs[i]) zsb.push_back(i);
int len = zsb.size();
for (int j = 0; j <= len - 1; j++) {
int t = zsb[j];
if (i*t > N) break;
iszs[i*t] = false;
mizs[i*t] = t;
if (i%t == 0) break;
}
}
ans[1] = 1;
for (int i = 2;i <= N;i++){
int t = mizs[i];
if (t<=1000 && (i%(t*t*t)==0)){
ans[i] = 0;
}else if (t<=10000&&(i%(t*t)==0)){
ans[i] = ans[i/(t*t)];
}else {
ans[i] = ans[i/t]*2;
}
}
for (int i = 2;i <= N;i++) ans[i] +=ans[i-1];
int T;
scanf("%d",&T);
while (T--){
int n;
scanf("%d",&n);
printf("%d\n",ans[n]);
}
return 0;
}
相关文章
- Vue 的网络请求
- java 舆情分析_基于Java实现网络舆情分析系统研究与实现.doc[通俗易懂]
- 腾讯星脉高性能计算网络:为AI大模型构筑网络底座
- 网络攻防对抗之“左右互搏术”
- 网络请求的缓存机制cachePolicy 和缓存的清理详解手机开发
- Linux系统预防网络入侵的检测方法(linux入侵检测系统)
- Linux下NS2安装指南:一步一步搭建你的网络仿真环境(linux下ns2安装)
- Linux虚拟机网络设置指南(linux虚拟机上网设置)
- Linux UDP穿透:实现跨网络互访(linuxudp穿透)
- 爱奇艺网络协程编写高并发应用实践
- Linux网络应聘指南:跨越面试关卡(linux网络面试题)
- 深入掌握Linux网络编程技术(Linux网络编程技术)
- 深入探索:Linux 中查看网络丢包率(linux 查看丢包率)