无平方因子数即对于任意一个素数p,p^2都不会整除那个数,如,3,5,7,15=3*5都是无平方因子数,而20=4*5=2^2*5不是!
先找素数,然后用容斥原理,递归求解
- 描述
-
In mathematics, a square-free integer is one divisible by no perfect square, expect 1.Such as 10,but 12 is not because 12=4×3.
So the problem is very simple, give you an interval [n,m],can should calculate how many square-free numbers in this interval?
- 输入
- Each line will consist of two integers n,m(0<n<=m<10^9),end by EOF.
- 输出
- Out put each answer in one line.
- 样例输入
-
1 10 10 20
- 样例输出
-
7 7
java代码nyoj 580:
import java.util.Scanner; public class Main { static int size=(int)Math.sqrt(999999999); static int prime[]=new int[size+10]; static boolean flag[]=new boolean[size+10]; static int count=0; public static void prim() { for(int i=2;i<=size;i++) { if(!flag[i]) { prime[count++]=i; for(int j=2*i;j<=size;j+=i) { flag[j]=true; } } } } //容斥原理 public static int dfs(int index,int num) { int sum=0; for(int i=index;i<count&&(prime[i]*prime[i])<=num;i++) { sum+=num/prime[i]/prime[i]-dfs(i+1, num/prime[i]/prime[i]); } return sum; } public static void main(String[] args) { prim(); Scanner scanner=new Scanner(System.in); while(scanner.hasNext()) { int n=scanner.nextInt(); int m=scanner.nextInt(); System.out.println(((m-dfs(0, m))-(n-dfs(0, n)))+1); } } }
uestc ac代码:
#include<stdio.h> #define size 1000005 int prime[size]; bool flag[size]; int count=0; void prim() { for(int i=2;i<=size;i++) { if(!flag[i]) { prime[count++]=i; for(int j=2;j*i<size;j++) { flag[j*i]=1; } } } } //容斥原理 long long int dfs(int index,long long int num) { long long int sum=0; for(int i=index;i<count&&(long long int)prime[i]*prime[i]<=num;i++) { sum+=num/prime[i]/prime[i]-dfs(i+1, num/prime[i]/prime[i]); } return sum; } int main() { int cases; prim(); scanf("%d",&cases); while(cases--) { long long int n; scanf("%lld",&n); printf("%lld\n",n-dfs(0,n)); } return 0; }