题目描述
如果一个数n，其素因子的个数为ω(n)，如果ω(n)是奇数，那么称其为“奇因数”。
比如，数60=22⋅3⋅5，ω(60)=3，那么60是“奇因数”。 显然，所有素数，必然是“奇因数”。
求区间[a,b]中“奇因数”的个数。
输入格式
第一行是一个整数T (1≤T≤10000)，表示样例的数量。
以后每行一个样例，为两个整数a,b,1≤a≤b≤106。
输出格式
每行输出一个样例的结果，为一个整数。
样例输入
2 1 10 1 100
样例输出
7 43
AC代码文章来源：https://www.toymoban.com/news/detail-802653.html
#include<stdio.h>
#define N 1000005
int a[N]={};
int f[N]={};
int w[N]={};
void init(){
int i,j;
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){
w[i]=1;
for(j=2;i*j<=N;j++){
w[i*j]++;
}
}
}
for(i=2;i<=N;i++){
if(w[i]%2!=0){
f[i]=1;
}
}
for(i=1;i<N;i++){
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();
}
}求质因数的个数，利用f[i*j]++，例如f[2]=1,则f[2*3]=1,f[3]=1,f[3*2]=f[6]++=2。求幂次次数，利用f[i*j]=f[i]+f[j]。例如f[2]=1,f[4]=f[2]+f[2]=2。文章来源地址https://www.toymoban.com/news/detail-802653.html
到了这里，关于xtu oj 1526 奇因数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
