PERIOD1 - Periodic function, trip 1

no tags 

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 3-periodic 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.


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 n-periodic 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.


Print the rank of this family ; ie the size of the largest collection of R-linearly independent elements of this family.





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 2017-02-11, after compiler changes)
I suspect there are several competitive approaches for this task.
Have fun ;-)

hide comments
[Rampage] Blue.Mary: 2016-02-20 03:48:10

Some ugly technique...

Francky: 2014-12-29 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...
If you find the image inappropriate, let's share, I can remove it.

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