2020HPU蓝桥杯省赛训练(一)

混份杯？根本混不上分好吧！！

A.算法提高 找素数

问题描述

给定区间[L, R] ， 请计算区间中素数的个数。

输入格式

两个数L和R。

输出格式

一行，区间中素数的个数。

样例输入

2 11

样例输出

5

数据规模和约定

2 <= L <= R <= 2147483647 R-L <= 1000000

思路

由于本题的数据范围较大，用暴力素筛的方法肯定会超时。首先我们要了解一个知识点就是任意一个数X，都会有一个小于sqrt(X)的质因子。由此条性质，我们可以先求区间(1,sqrt(R))中的质数，然后依次对每个质数进行操作，可以求出(L,R)中的合数。最后将(L,R)之间的合数映射到(0,R-L)之间，防止超内存。

AC code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l,r;
int a[1000000];
ll b[1000000];
int c[1000000];
int main()
{
	cin>>l>>r;
	int m=sqrt(r);
	memset(a,0,sizeof a);
	memset(c,0,sizeof c);
	a[2]=0;a[1]=1;
	int cnt=0;
	for(int i=2;i<=m;i++)
	{
		if(a[i]==0) b[++cnt]=i;
		for(int j=2*i;j<=m;j+=i)
		{
			a[j]=1;
		}
	}
//	for(int i=1;i<=cnt;i++)
//	{
//		printf("%d..",b[i]);
//	}
	int ans=0;
	for(int i=1;i<=cnt;i++)
	{
			for(ll j=max(b[i]*2,l/b[i]*b[i]);j<=r;j+=b[i])
			{
				if(j>=l)
				{
					c[j-l]=1;
					//printf("%d..",j);				
				}
			} 
	}
	for(int i=0;i<=r-l;i++)
	{
		if(c[i]==0) ans++;
	}
	printf("%d\n",ans);
	return 0;
}

E 基础练习 十六进制转八进制

问题描述

给定n个十六进制正整数，输出它们对应的八进制数。

输入格式

输入的第一行为一个正整数n （1<=n<=10）。
接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。

输出格式

输出n行，每行为输入对应的八进制正整数。

【注意】

输入的十六进制数不会有前导0，比如012A。
输出的八进制数也不能有前导0。

样例输入

2
39
123ABC

样例输出

71
4435274

思路

先将16进制转换为2进制再转化为16进制。注意每一个数在不同进制中的映射关系。

AC code

#include<bits/stdc++.h>
using namespace std;
string s;
int a[1000000];
int b[1000000];
int c[1000000];
int n;
int main()
{
	cin>>n;
	while(n--)
	{
		cin>>s;
		for(int i=0;i<s.length();i++)
		{
			if(s[i]>='0'&&s[i]<='9') a[i]=s[i]-'0';
			else a[i]=s[i]-'A'+10;
		} 
//		printf("%d..\n",a[0]);
		int k=(s.length())*4;
		for(int i=s.length()-1;i>=0;i--)
		{
			for(int j=1;j<=4;j++)
			{
				b[k--]=a[i]%2;
				a[i]=a[i]/2;
			}
		}
		if(((s.length())*4)%3==0) k=((s.length())*4)/3;
		else k=((s.length())*4)/3+1;
		int kk=k;
		for(int i=(s.length())*4;i>=1;)
		{
			int j=1;c[k]=0;
			while(i>=1&&j<=3)
			{
				if(b[i]==1)
				c[k]=c[k]+pow(2,j-1);
				i--;j++;
			}
			k--;
		}
		int i;
		for(i=1;i<=kk;i++)
		{
			if(c[i]!=0) break;
		}
		for(int j=i;j<=kk;j++)
		printf("%d",c[j]);
		printf("\n");
	}
}

G 算法提高 欧拉函数

问题描述

给定一个大于1，不超过2000000的正整数n，输出欧拉函数，phi(n)的值。欧拉函数phi(n)是数论中非常重要的一个函数，其表示1到n-1之间，与n互质的数的个数。

思路

可以利用类似素筛的方法将每一个数的phi值找到

#include<bits/stdc++.h>
using namespace std;
int a[2000000+100];
int n;
int main()
{
	cin>>n;
	memset(a,0,sizeof a);
	a[1]=1;a[2]=0;
	for(int i=2;i<=2000000;i++)
	{
		if(!a[i])
		for(int j=i;j<=2000000;j+=i)
		{
			if(!a[j]) a[j]=j;
			a[j]=a[j]/i*(i-1);
		} 
	}
	printf("%d",a[n]);
}

打赏