做网站总费用,自己做的网站为什么访问不,html网站登录界面模板下载,软文推广产品Factorization 题目描述 根据质因子唯一分解定理可知npk11pk22…pkmm#xff0c;其中pi都是质数。我们定义f(n)m, 求g(a,b)∑biaf(i)。
输入 第一行是一个整数T(1≤T≤1000)#xff0c;表示样例的个数。
以后每个样例占一行#xff0c;为两个整数 a(2≤a≤b≤106)。
输出…Factorization 题目描述 根据质因子唯一分解定理可知npk11pk22…pkmm其中pi都是质数。我们定义f(n)m, 求g(a,b)∑biaf(i)。
输入 第一行是一个整数T(1≤T≤1000)表示样例的个数。
以后每个样例占一行为两个整数 a(2≤a≤b≤106)。
输出 依次每行输出一个样例的结果为一个整数。
样例输入 2 2 2 2 10 样例输出 1 11
AC代码
#includestdio.h
#define N 1000005
int a[N]{};
int f[N]{};
void init(){int i,j,cnt0;a[0]1,a[1]1;for(i2;i*iN;i){if(a[i]0){for(j2*i;jN;ji){a[j]1;}}}for(i2;iN;i){if(a[i]0){f[i]1;for(j2;i*jN;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。本题还利用前缀和知识。
