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.
Input: 3 1 1000 100000000000000 Output: 1 608 60792710185947Warning: A naive algorithm will probably not be sufficient to be accepted.
A naive algorithm
It's so crazy!
mobius is enough...
nlogn is sufficient to get Accepted.
Finally AC :), nice problem i had to improve my mu function in nloglogn
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 source limit is too strict. Even a solution of size 1946 bytes was rejected.
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
Finally I got AC. Need a lot of optimizations to solve this problem.
don't think you can get rid of divisions. at least I can't think of any way to do this.
|Added by:||Robert Gerbicz|
|Cluster:||Cube (Intel G860)|
|Languages:||All except: ERL JS-RHINO|
|Resource:||classic, own input|