xtu oj 1526 奇因数

发布时间:2024年01月12日

题目描述

如果一个数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代码

#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://blog.csdn.net/m0_75005390/article/details/135545980
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。