SQFREE - Square-free integers

In number theory we call an integer square-free if it is not divisible by a perfect square, except 1. You have to count them!


First line contains an integer T, the number of test cases (T≤100). The following T lines each contains one positive integer: n, where n ≤ 1014


T lines, on each line output the number of (positive) square-free integers not larger than n.



Warning: A naive algorithm probably not works.

hide comments
xiaoyimi: 2017-01-05 03:53:18

It's so crazy!
I don't think this problem can be accepted by O(T√n)!

cccsober: 2016-06-26 13:11:40

mobius is enough...

Scape: 2015-09-21 15:53:07

nlogn is sufficient to get Accepted.

Who: 2014-11-25 11:58:35

Finally AC :), nice problem i had to improve my mu function in nloglogn

:D: 2012-08-31 06:19:12

The limit is sensible since a lot of users passed it and it's a setters decision to make it strict. And are you sure you had 1946B, not 1,9KB for example? From what I checked it works fine.

The only thing I would complain about is that it should be always mentioned in the description. Since 95% of the time there is 50000B, I don't even pay attention to it and it comes out when trying to commit.

Raghavendran Ramachandran: 2012-08-31 05:13:53

The source limit is too strict. Even a solution of size 1946 bytes was rejected.

(Tjandra Satria Gunawan)(曾毅昆): 2012-07-30 08:41:46

Finally I got AC. Need a lot of optimizations to solve this problem.

Gogu: 2009-05-17 20:44:35

don't think you can get rid of divisions. at least I can't think of any way to do this.

[Trichromatic] XilinX: 2009-04-06 13:39:37

I've no idea about that.

amaroq: 2009-04-06 08:34:59

Is there a way to avoid division in the second part of the solution? Most of my code's time is spent on dividing long longs.
To prevent spoiling the problem, please only answer 'yes' or 'no'.

Added by:Robert Gerbicz
Time limit:2.177s
Source limit:2009B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:classic, own input