数(aqnum)

数(aqnum)

3.1 题目描述

秋锅对数论很感兴趣，他特别喜欢一种数字。秋锅把这种数字命名为农数，英文名为 AQ number 。

这种数字定义如下：

定义 1 一个数 n 是农数，当且仅当对于每个质数 p ，要么 p ∤ n ，要么 p ≤ MAXPRIME

且存在一个正奇数 k 使得 p k | n 且 p k+1 ∤ n 。

秋锅想知道，给定 N,MAXPRIME ，问 1 到 N 里面的农数有多少个呢？

3.2 输入格式

一行 2 个数，

分别为 N 和 MAXPRIME 。

3.3 输出格式

一行一个数，表示 1 到 N 中农数的个数。

3.4 样例输入

10 3

3.5 样例输出

3.6数据范围

对于 30% 的数据：N ≤ 1000

对于 60% 的数据：N ≤ 5 × 10^6

对于 100% 的数据：N ≤ 10^10 ，MAXPRIME ≤ 10^6

题解：

搜索。怎么能想到它是搜索呐？

农数的因数满足小于等于maxprime,且指数为奇数，处理出小于等于maxprime的质数，枚举指数的情况，加一个剪枝，如果当前数*pri[i]^2>limit,停止搜索，二分一个最大的乘以当前数<=limi的质因子，答案加上这些质子，注意数据范围(最近总是忽略数据范围)。

写的时候，一直把upper_bound写成了lower_bound，傻傻分不清。

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

using namespace std;

int pri[1000010];

long long sum=0,lim,ma,p;

bool o[1000010];

long long read()

{

	long long ans=0,fu=1;char ch=getchar();

	while(!isdigit(ch)) {if(ch=='-') fu=-1;ch=getchar();}

	while(isdigit(ch)) {ans=ans*10+ch-'0';ch=getchar();}

	return ans*fu;

}

void prime(int x)

{

	p=0;

	o[1]=1;

	for(int i=2;i<=x;i++)

	{

		if(!o[i])

		  pri[++p]=i;

		for(int j=1;j<=p&&pri[j]*i<=x;j++)

		{

			o[pri[j]*i]=1;

			if(i%pri[j]==0)

			  break;

		}

	}

}

void search(long long x,int th)            //x要开long long哦

{

	if(th==p+1)

	{

		sum++;

		return;

	}

	if(x*pri[th]>lim)

	{

		sum++;

		return;

	}

	if(x*pri[th]*pri[th]>lim)

	{

		int pos=upper_bound(pri+1,pri+p+1,lim/x)-pri;

		sum+=pos-th+1;

		if(sum<0)

		{

			int debug=1;

		}

		return;

	}

	search(x,th+1);

	for(int i=0;;i++)

	{

		if(x>lim)

		  return;

		if(i&1)

		  search(x,th+1);

		x*=pri[th];

	}

}

int main()

{

	freopen("aqnum.in","r",stdin);

	freopen("aqnum.out","w",stdout);

	lim=read(),ma=read();

	prime(ma);

	search((long long)1,1);

	printf("%lld",sum);

	return 0;

}

巴特西

数(aqnum)

最新文章

热门文章