线性筛求积性函数

题目链接：登录—专业IT笔试面试备考平台_牛客网

样例输入： 

5
1
2
3
4
5

样例输出：

1
2
2
3
2

分析：我们可以对q个询问进行暴力求解，每次询问的复杂度就是O(n^0.5)，那么总的复杂度就是q*n^0.5，大概是10^8.5，估计过不了，况且如果对于别的题，询问组数再多一些，那么就铁定过不了了。

设f[n]表示n的所有正因数的个数，那么f[n]是一个积性函数，如果不知道积性函数或者不知道为什么f[n]是一个积性函数的话可以看一下：积性函数_AC__dream的博客-CSDN博客

我们可以通过线性筛直接O(n)预处理出来所有的f[n]，直接对于每组询问O(1)查询即可。

过程由于在之前积性函数那篇博客中已经讲解的非常明白了，这里就不赘述了

下面是代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=1e7+10;
bool vis[N];
int prime[N],tt,f[N];
int cnt[N];//cnt[i]记录i的最小质因子的次数 
void init()
{
	f[1]=1;
	for(int i=2;i<N;i++)
	{
		if(!vis[i])
		{
			prime[++tt]=i;
			f[i]=2;
			cnt[i]=1;
		}
		for(int j=1;j<=tt&&i*prime[j]<N;j++)
		{
			vis[i*prime[j]]=true;
			if(i%prime[j]==0)//prime[j]是i的最小质因子 
			{
				cnt[i*prime[j]]=cnt[i]+1;
				f[i*prime[j]]=f[i]/(1+cnt[i])*(2+cnt[i]);
				break;
			}
			cnt[i*prime[j]]=1;
			f[i*prime[j]]=f[i]*f[prime[j]];
		}
	}
}
int main()
{
	int q;
	init();
	cin>>q;
	while(q--)
	{
		int n;
		scanf("%d",&n);
		printf("%d\n",f[n]);
	}
	return 0;
}