计蒜客 30999 - Sum - [找规律+线性筛][2018ICPC南京网络预赛J题]

时间:2024-08-03 17:34:20

题目链接:https://nanti.jisuanke.com/t/30999

计蒜客 30999 - Sum - [找规律+线性筛][2018ICPC南京网络预赛J题]

样例输入
2
5
8

样例输出
8
14

题意:

squarefree数是指不含有完全平方数( 1 除外)因子的数,

现在一个数字 $n$,可以表示成两个squarefree数 $a,b$ 相乘,即 $n = ab$,

假设 $f\left( n \right)$ 代表了 $n$ 分解成不同的数对 $\left( {a,b} \right)$ 的个数,

现在给你一个 $n$,要求 $f\left( 1 \right) + f\left( 2 \right) + \cdots + f\left( n \right)$。

题解:

不难发现,若 $n$ 含有一个因子是立方数乃至更高次方数,则此时 $f\left( n \right) = 0$,例如 $f\left( {2^3 \times 3} \right) = 0,f\left( {3^4 } \right) = 0$;

则剩下来的数,因子最多就是平方数,不妨举些例子来看每个因子能提供多少贡献:

最开始是 $f\left( 1 \right) = 1$,因为只有 $1 = 1 \times 1$,然后我们给它乘上一些因子……

  1、乘上指数为 $1$ 的因子,例如 $f\left( {1 \times 2} \right)$,加进来的 $2$ ,可以添加在原来$1 \times 1$的乘号左边($2 \times 1$),也可以添加在右边($1 \times 2$),所以贡献了“$\times 2$”,即 $f\left( {1 \times 2} \right) = f\left( 1 \right) \times 2$;

  2、乘上指数为 $2$ 的因子,例如 $f\left( {1 \times 2^2 } \right)$,加进来的 $2^2$,它不能全部添加在某一边,只能拆开来,一半添加在乘号左边,一半添加在乘号右边,即$2 \times 2$,所以贡献了“$\times 1$”,即 $f\left( {1 \times 2^2} \right) = f\left( 1 \right) \times 1$。

那么依次类推,再在后面乘上一些因子,同样的道理,指数为 $1$ 则贡献为“$\times 2$”,指数为 $2$ 则贡献为“$\times 1$”。

很容易的就能得到递推规律:假设 $n$ 的最小素因子是 $p$,则有 $n = m \times p^x$,我们分两种情况讨论:

  1、$x = 1$,$p$ 的贡献为“$\times 2$”,就有 $f\left( n \right) = f\left( m \right) \times 2$;

  2、$x = 2$,$p$ 的贡献为“$\times 1$”,就有 $f\left( n \right) = f\left( m \right)$;

那么,现在的关键就是求得 $1$ 到 $2 \times 10^7$ 的每个数字的最小素因子,线性筛素数的时候可以顺带求出。

AC代码:

#include<bits/stdc++.h>
using namespace std; const int maxn=2e7+;
const int MAX=2e7; int n;
int mpf[maxn]; //存储最小素因子 /************************** 线性筛 - st **************************/
int prime[maxn];
bool isPrime[maxn];
void Screen() //欧拉筛法求素数
{
register int cnt=;
memset(isPrime,,sizeof(isPrime));
isPrime[]=isPrime[]=;
for(int i=;i<=MAX;i++)
{
if(isPrime[i]) prime[cnt++]=i, mpf[i]=i;
for(int j=;j<cnt;j++)
{
if(i*prime[j]>MAX) break;
isPrime[i*prime[j]]=, mpf[i*prime[j]]=prime[j];
if(i%prime[j]==) break;
}
}
}
/************************** 线性筛 - ed **************************/ long long f[maxn]; int main()
{
Screen(); f[]=;
for(int i=;i<=MAX;i++)
{
int mm = mpf[i];
if((long long)mm*mm < MAX && (long long)mm*mm*mm < MAX && i%(mm*mm*mm) == ) f[i]=;
else if((long long)mm*mm < MAX && i%(mm*mm) == ) f[i]=f[i/mm/mm];
else f[i]=*f[i/mm];
}
for(int i=;i<=MAX;i++) f[i]+=f[i-]; int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
printf("%lld\n",f[n]);
}
}