牛客小白月赛39: G题 冷静
https://ac.nowcoder.com/acm/contest/11216/G
听了一遍题解试着敲竟然写出来了,分享一下~
标签:欧拉筛 + 转换 + 树状数组 + 离线
分析:(欧拉筛 + 转换 + 离线 + 树状数组)
1.先转换题意:转换一下就是求1~n中有多少个数可以分解为若干个质数相乘且质数>=k, 也就是问有1~n中有多少个数的最小质因子>=k
2.先解决质因子的问题:可以用欧拉筛先把1~maxn中每个数的最小质因子筛出来
3.离线,把询问按n从小到大排序,建 维护 树状数组,树状数组树的值d[x]表示的就是1-ni中最小质因子是x的数的个数(至于为什么要离线我也不太懂,为了后面的树状数组操作?和降低时间复杂度?)
4.维护:当u < ni时,就维护(想清楚维护的是什么,树状数组维护的是最小质因子相同的数的个数),所以add(f[u],1);其中f[u]是u的最小质因子,就是在它的最小质因子的地方个数+1
4.对于询问,再查询,查询的其实就是ki-ni的树值的和
5.需要注意的是,cin会超时,优化之后还是会...所以用scanf
补学知识点:1.二维偏序问题!!!
2.欧拉筛求1~n最小质因数
3.离线操作
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<cmath>
#include<algorithm>
#include<deque>
#include<sstream>
#include<set>
#include<stack>
#include<bitset>
#include<unordered_map>
#define you_hua ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
//ios::sync_with_stdio(false);
//cin.tie(0);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int maxn=4e6+7;
const int N = 1e5+7;
const int mod=1e9+7;
const int inf=1e9+7;
const double pi = 3.1415926;
const double eps = 1e-6;
int d[maxn]; //树状数组
int f[maxn]; //存每个数的最小质因数
int prime[maxn]; //存质数
int vis[maxn];
int ans[maxn]; //存答案
int cnt;
struct node //为了下面的离线操作
{
int n,k,idx;
}no[maxn];
bool cmp(node a,node b)
{
return a.n < b.n;
}
void init(int n) //欧拉筛求1~n中每个数的最小质因数
{
memset(vis,0,sizeof(vis));
for (int i = 2;i <= n; i++)
{
if (!vis[i])
{
prime[++prime[0]]=i;
f[i]=i;
}
for (int j = 1; j <=prime[0] && i*prime[j] <=n; j++)
{
vis[i*prime[j]] = 1;
f[i*prime[j]]=prime[j];
if (i % prime[j] == 0)
{
break;
}
}
}
}
//下面是树状数组操作
int lowbit(int x)
{
return x & -x;
}
void add(int x,int v) //添加操作,在这个最小质因子的个数+1
{
while(x <= 3e6) //注意这里到哪
{
d[x] += v;
x += lowbit(x);
}
}
int query(int x) //查询操作
{
int ans=0;
while(x)
{
ans += d[x];
x -= lowbit(x);
}
return ans;
}
int main()
{
init(maxn); //欧拉筛
// for(int i=2;i<=100;i++) cout<<i<<' '<<f[i]<<endl;
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d %d",&no[i].n,&no[i].k);
no[i].idx = i;
}
sort(no+1,no+1+q,cmp); //按照n从大到小排序
int u=2; //从1开始
for(int i=1;i<=q;i++)
{
// cout<<no[i].n<<endl;
while(u <= no[i].n) //一直更新
{
// cout<<f[u]<<endl;
add(f[u],1); //在u的最小质因子的地方+1
u++;
}
// cout<<"---"<<endl;
ans[no[i].idx] = query(no[i].n) - query(no[i].k-1); //树状数组区间查询操作
}
for(int i=1;i<=q;i++)
printf("%d\n",ans[i]);
return 0;
}