題目描述
如果一個(gè)數(shù)n，其素因子的個(gè)數(shù)為ω(n)，如果ω(n)是奇數(shù)，那么稱其為“奇因數(shù)”。
比如，數(shù)60=22?3?5，ω(60)=3，那么60是“奇因數(shù)”。 顯然，所有素?cái)?shù)，必然是“奇因數(shù)”。
求區(qū)間[a,b]中“奇因數(shù)”的個(gè)數(shù)。
輸入格式
第一行是一個(gè)整數(shù)T?(1≤T≤10000)，表示樣例的數(shù)量。
以后每行一個(gè)樣例，為兩個(gè)整數(shù)a,b,1≤a≤b≤106。
輸出格式
每行輸出一個(gè)樣例的結(jié)果，為一個(gè)整數(shù)。
樣例輸入
2 1 10 1 100
樣例輸出
7 43
AC代碼文章來源：http://www.zghlxwxcb.cn/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();
}
}求質(zhì)因數(shù)的個(gè)數(shù)，利用f[i*j]++，例如f[2]=1,則f[2*3]=1,f[3]=1,f[3*2]=f[6]++=2。求冪次次數(shù)，利用f[i*j]=f[i]+f[j]。例如f[2]=1,f[4]=f[2]+f[2]=2。文章來源地址http://www.zghlxwxcb.cn/news/detail-802653.html
到了這里，關(guān)于xtu oj 1526 奇因數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
