xtu oj 1377 Factorization

本文主要是介绍xtu oj 1377 Factorization，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Factorization
题目描述
根据质因子唯一分解定理可知n=pk11pk22…pkmm，其中pi都是质数。我们定义f(n)=m, 求g(a,b)=∑bi=af(i)。

输入
第一行是一个整数T(1≤T≤1000)，表示样例的个数。

以后每个样例占一行，为两个整数 a(2≤a≤b≤106)。

输出
依次每行输出一个样例的结果，为一个整数。

样例输入
2
2 2
2 10
样例输出
1
11

AC代码

#include<stdio.h>
#define N 1000005
int a[N]={}; 
int f[N]={};
void init(){int i,j,cnt=0;a[0]=1,a[1]=1;for(i=2;i*i<=N;i++){if(a[i]==0){for(j=2*i;j<=N;j+=i){a[j]=1;}}}for(i=2;i<=N;i++){if(a[i]==0){f[i]=1;for(j=2;i*j<=N;j++){f[i*j]++;}}f[i]+=f[i-1];} 
}
void sol(){int a,b;scanf("%d%d",&a,&b);printf("%d\n",f[b]-f[a-1]);
}
int main()
{int T;scanf("%d",&T);init();while(T--){sol();}} 

解题思路：埃筛筛选素数，如果i为素数，则素因子个数为1。此题的巧妙处在于f[i*j]++。比如f[6],f[2]=1,f[2*3]=1;f[3]=1,f[2*3]=1,所以f[6]=2。本题还利用前缀和知识。

这篇关于xtu oj 1377 Factorization的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---