问题描述
由于两个数字 X 和是，发现是无平方数的计数，其中无平方数是整除没有完美的广场上，除了 1 。例如， 10 是方形的，免费的，但 18 不是，因为它是整除 9 = 32 。一些积极广场的免费电话号码是：
Given two numbers x and y , find count of numbers that are squarefree where squarefree number is one divisible by no perfect square, except 1. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 32. Few positive square-free numbers are :
1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15 ...
限制
1 <= X,Y <= 10^9
0 <= |X-Y| <= 10^6
x=10 , Y=15
给
ans=5
我的做法是生成所有素，直到平方根（10 ^ 9）（埃拉托色尼筛），并检查是否每个数字在给定范围内整除主要广场。伯爵这样的数字是从范围长度减去给方免费电话号码。
My approach is to generate all prime till squareroot(10^9) (sieve of eratosthenes), and check whether each number in given range divisible by square of prime . Count of such numbers is substracted from length of range to give square free numbers .
但这种方法超时的复杂性，请提出了一些其他的方法
But this approach time out in complexity , please suggest some other approach
推荐答案
使用容斥原理：
让 F（N）= 1的非方形免费电话号码... N 。我们将仅做素数的平方容斥，从而避免超量为正方形的平方
Let f(n) = number of non-square-free numbers in 1 ... n. We will only do inclusion-exclusion on the squares of primes, so as to avoid overcounting for squares of squares.
我们有：
f(n) = n / 4 => these are divisible by 4, so NOT square-free
+
n / 9 => these are divisible by 9, so NOT square-free
+
n / 25 => these are divisible by 16, so NOT square-free
+
...
-
n / (4*9) => these are divisible by both 4 and 9, so we overcounted
-
n / (4*25) => these are divisible by both 4 and 25, so we overcounted
-
...
如何有效的是什么？
How efficient is this?
我们只需要素数 P ，使得点^ 2'= 10 ^ 9 ，这意味着 P＆LT; 31623 。这已经不是很多素数，任何微不足道的筛（或者甚至审判庭）要足够快。然后应用容斥，这也将是快速的，因为平方素数的产品将获得较大的快，所以你就可以pmaturely终止$ P $在AA很多情况下（的N /某事= 0 每当的东西和GT; N ）
We only need primes p such that p^2 <= 10^9, meaning p < 31623. This already isn't a lot of primes, any trivial sieve (or maybe even trial division) should be fast enough. Then apply inclusion-exclusion, which will also be fast since the products of squared primes will get large fast so you'll be able to terminate prematurely in a a lot of cases (n / something = 0 whenever something > n).
为了明白为什么你就可以终止prematurely，改写上面：
In order to see why you'll be able to terminate prematurely, rewrite the above as:
f(n) = n / (2^2) -
n / (2^2*3^2) +
n / (2^2*3^2*5^2) - <= this becomes 0 very fast.
When it does,
backtrack and increment the previous term.
For example, if this were 0,
you'd do - n / (2^2*5^2) next
...
在此这里更多信息。
这篇关于算上无平方数的范围内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！