ACM-ICPC 2018 南京赛区网络预赛__J. Sum【欧拉筛法+质因子分解+思维】

本文主要是介绍ACM-ICPC 2018 南京赛区网络预赛__J. Sum【欧拉筛法+质因子分解+思维】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  •  1000ms
  •  512000K

A square-free integer is an integer which is indivisible by any square number except 1. For example, 6=2⋅3 is square-free, but 12=2^2⋅3 is not, because 2^2 is a square number. Some integers could be decomposed into product of two square-free integers, there may be more than one decomposition ways. For example, 6=1⋅6=6⋅1=2⋅3=3⋅2,n=ab and n=ba are considered different if a̸=b.f(n) is the number of decomposition ways that n=ab such that a and b are square-free integers. The problem is calculating f(1)+f(2)+...+f(n).

Input

The first line contains an integer T(T≤20), denoting the number of test cases.

For each test case, there first line has a integer n(n≤2⋅10^7).

Output

For each test case, print the answer f(1)+f(2)+...+f(n) .

Hint

∑​f(i)=f(1)+⋯+f(8)
=1+2+2+1+2+4+2+0=14=1+2+2+1+2+4+2+0=14.

样例输入

2
5
8

样例输出

8
14

题目来源

ACM-ICPC 2018 南京赛区网络预赛

题目大意:f(n)定义为n=a*b这样分解的式子数,其中a和b不能包含平方因子。当a!=b时n=a*b和n=b*a视为两个式子。t 组测试,n表示所求结果为 f(1)+f(2)+f(3)+...+f(n)

题解:有如下结论

1.若i是素数则f(i)=2

2.若i的某个质因子个数超过2,则f(i)=0。这个结论很好想,如果有大于2个相同质因子,那么对于i的每个分解 i=a*b,a和b中必定有一个数含平方因子

3.若i=a*b且a和b不含相同因子即可,那么f(i)=f(a)*f(b)

4.若i的质因子x的个数为2,f(i)=f(i/(x*x))即为去掉平方因子的个数

打表用到了欧拉筛法

AC的C++代码:

#include<iostream>using namespace std;
const int N=2e7+5;int prime[N];//存储连续素数,prime[0]表示连续素数的个数
bool vis[N];
int f[N];//结果void solve()
{f[1]=1;for(int i=2;i<N;i++){if(!vis[i]){prime[++prime[0]]=i;//存储这个素数 f[i]=2;//素数的结果为2 }for(int j=1;j<=prime[0]&&prime[j]*i<N;j++){int x=prime[j]*i;vis[x]=true;//标记x为合数 if(i%prime[j])//若i=a*b且a和b不含相同因子即可,那么f(i)=f(a)*f(b)f[x]=f[prime[j]]*f[i];else{//如果prime[j]是i的最小质因子 if(i%(prime[j]*prime[j])==0)//如果x的某个质因子个数超过2则f[i]=0 f[x]=0;else//如果x的某个质因子个数为2,则答案为去掉平方项的结果 f[x]=f[x/(prime[j]*prime[j])];break;//欧拉筛法保证每个合数只被它的最小质因子筛去,因此要跳出 }}}//前缀和 for(int i=1;i<N;i++)f[i]+=f[i-1];
}int main()
{int t,n;solve();scanf("%d",&t);while(t--){scanf("%d",&n);printf("%d\n",f[n]);}return 0;
}

解法二

#include<iostream>using namespace std;typedef long long ll;
const int N=20000007;int prime[N+1];
ll f[N+1];void solve(int n)
{f[1]=1;for(int i=2;i<=n;i++){if(!prime[i]){prime[++prime[0]]=i;f[i]=2;}for(int j=1;j<=prime[0]&&prime[j]<=n/i;j++){prime[i*prime[j]]=1;if(i%prime[j]){f[i*prime[j]]=f[i]*2;}else//i%prime[j]==0{if((i/prime[j])%prime[j]==0)f[i*prime[j]]=0;elsef[i*prime[j]]=f[i/prime[j]];break;}}}for(int i=2;i<=n;i++)f[i]+=f[i-1];
}int main()
{int t,n;solve(N);scanf("%d",&t);while(t--){scanf("%d",&n);printf("%lld\n",f[n]);}return 0;
}

 

这篇关于ACM-ICPC 2018 南京赛区网络预赛__J. Sum【欧拉筛法+质因子分解+思维】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/626500

相关文章

SSID究竟是什么? WiFi网络名称及工作方式解析

《SSID究竟是什么?WiFi网络名称及工作方式解析》SID可以看作是无线网络的名称,类似于有线网络中的网络名称或者路由器的名称,在无线网络中,设备通过SSID来识别和连接到特定的无线网络... 当提到 Wi-Fi 网络时,就避不开「SSID」这个术语。简单来说,SSID 就是 Wi-Fi 网络的名称。比如

Java实现任务管理器性能网络监控数据的方法详解

《Java实现任务管理器性能网络监控数据的方法详解》在现代操作系统中,任务管理器是一个非常重要的工具,用于监控和管理计算机的运行状态,包括CPU使用率、内存占用等,对于开发者和系统管理员来说,了解这些... 目录引言一、背景知识二、准备工作1. Maven依赖2. Gradle依赖三、代码实现四、代码详解五

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

ASIO网络调试助手之一:简介

多年前,写过几篇《Boost.Asio C++网络编程》的学习文章,一直没机会实践。最近项目中用到了Asio,于是抽空写了个网络调试助手。 开发环境: Win10 Qt5.12.6 + Asio(standalone) + spdlog 支持协议: UDP + TCP Client + TCP Server 独立的Asio(http://www.think-async.com)只包含了头文件,不依

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

目录   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点:弱密码字典爆破 四种方法:   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 访问环境 老规矩,我们先查看源代码

poj 3181 网络流,建图。

题意: 农夫约翰为他的牛准备了F种食物和D种饮料。 每头牛都有各自喜欢的食物和饮料,而每种食物和饮料都只能分配给一头牛。 问最多能有多少头牛可以同时得到喜欢的食物和饮料。 解析: 由于要同时得到喜欢的食物和饮料,所以网络流建图的时候要把牛拆点了。 如下建图: s -> 食物 -> 牛1 -> 牛2 -> 饮料 -> t 所以分配一下点: s  =  0, 牛1= 1~

poj 3068 有流量限制的最小费用网络流

题意: m条有向边连接了n个仓库,每条边都有一定费用。 将两种危险品从0运到n-1,除了起点和终点外,危险品不能放在一起,也不能走相同的路径。 求最小的费用是多少。 解析: 抽象出一个源点s一个汇点t,源点与0相连,费用为0,容量为2。 汇点与n - 1相连,费用为0,容量为2。 每条边之间也相连,费用为每条边的费用,容量为1。 建图完毕之后,求一条流量为2的最小费用流就行了

poj 2112 网络流+二分

题意: k台挤奶机,c头牛,每台挤奶机可以挤m头牛。 现在给出每只牛到挤奶机的距离矩阵,求最小化牛的最大路程。 解析: 最大值最小化,最小值最大化,用二分来做。 先求出两点之间的最短距离。 然后二分匹配牛到挤奶机的最大路程,匹配中的判断是在这个最大路程下,是否牛的数量达到c只。 如何求牛的数量呢,用网络流来做。 从源点到牛引一条容量为1的边,然后挤奶机到汇点引一条容量为m的边