PERIOD1  Periodic function, trip 1
Let us consider periodic functions from Z to R.
def f(x): return [4, 6, 7][x%3] # (with Python notations) # 4, 6, 7, 4, 6, 7, 4, 6, 7, 4, 6, 7, 4, 6, 7, ...
For example, f is a 3periodic function, with f(0) = f(3) = f(6) = f(9) = 4.
With a simplified notation we will denote f as [4, 6, 7].
For two periodic functions (with integral period), here the quotient of periods will be rational, in that case it can be shown that the sum of the functions is also a periodic function.
Thus, the set of all such functions is a vector space over R.
Our interest, in this problem, will be the dimension of this space when the period is bounded by some integer N.
Input
The first line contains an integer T, the number of test cases.
On the next T lines, you will be given an integer N.
Consider the family of all nperiodic functions for n in [1..N].
There are some links between some functions.
For example: [2, 0] = [2, 0, 1, 0] + [0, 0, 1, 0], with simplified notations.
Output
Print the rank of this family ; ie the size of the largest collection of Rlinearly independent elements of this family.
Example
Input: 3 2 3 4 Output: 2 4 6
Constraints
0 < T < 10^2 0 < N < 10^8
There's two input files, one easy (mostly small input), and a hard one (uniform random input).
My PY3.4 code get AC in 0.02+0.55=0.57s. This code isn't optimized. (edited 20170211, after compiler changes)
I suspect there are several competitive approaches for this task.
Have fun ;)
hide comments
[Rampage] Blue.Mary:
20160220 03:48:10
Some ugly technique... 

Francky:
20141229 22:26:13
I plan 3 different trips with periodic functions. This one isn't easy, the next one should be easy, and the third very hard or extreme...

Added by:  Francky 
Date:  20141229 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 