Need ideas

[jumper007]

I have started to train for the school exams, and I came across this one specific problem. I have no idea how to start solving it. Any help or ideas are highly appreciated.

Problem: Subsequence 2
On the date of 20.12.2012, an important national day, Piftel has dreamt 2 integers N and K which could lower the probability for the world to end, if Piftel can solve the following problem. He is given the integers from 1 to N and has to find out the longest subsequence in which the sum of any 2 elements (integers) of the subsequence is not divisible by K. As he just woke up, and it's already 21.12.2012, he has to find out the answer to this question very fast, so he asks for your help.

Input: The file "subsequence2.in" will contain on the first line separated by a space the two integers N and K.

Output: The file "subsequence2.out" will contain on the first line the number representing the length of the longest subsequence which follows the given rules.

Restrictions: 1 ≤ K ≤ N ≤ 2.000.000.000
Time Limit / test: 0.1 seconds
Memory Limit: 16384 kbytes

Example:

subsequence2.in
9 3

subsequence2.out
4

As the time limit is 0.1 seconds and the numbers N and K can reach long long, I suppose it has to be solved mathematically.
I found a formula, but I am not sure if this is right:
maxLength = (N - powf(N, 1/K)) / 2 + 1;
The only problem is that the powf function doesn't work as I expected.
................................................................3 __
Example: N = 9, K = 3, maxLength = (9 - \/9 ) / 2 + 1 = (9 - 2) / 2 + 1 = 7 / 2 + 1 = 3 + 1 = 4
Though, I am not sure it's gonna work for any N and K.

Sorry if I was confusing.
If you have any ideas, please let me know.
Thanks in advance,
~ Raul ~

[ne555]

For n=12, k=3
your formulae gives (12-2)/2+1 = 5+1 = 6
But I could only get 5: 2 3 5 8 11

It could help if you say how did you obtain that equation.

[jumper007]

Well, it was just the first thing that crossed my mind. I knew I had to use both N and K in finding out the max length. The first formula I used was K / 2 + 1 which didn't give the right results (I used that one because I thought that a subsequence can only be formed with consecutive numbers eg: N = 9 K = 4 Max Sequence: 4, 5, 6). As I found out that this wasn't good (not for the actual task), I tried out many things, and decided to stop on the once I posted because it was the only one which gave the right answer for their given example.. I know this most probably sounds fail.. But I have no mathematical explanation for my formula. It was just something random. :/

PS: If there wasn't such a low time limit and the restrictions were not long long, this could be solved using backtracking though, but taking into consideration all the restrictions, not even a greedy approach would work. So, it has to be done mathematically I guess..

[ne555]

You'll need some modulo background
(a+b) mod m = (a mod m + b mod m) mod m

> in which the sum of any 2 elements (integers) of the subsequence is not divisible by K
So we have a set of points, we choice 2 and test if the sum is divisible

The sum will be divisible if the modulo is 0.
Now, ¿how can this happen?

Let's operate in the set and compute the modulo of all the numbers (now we will have repeated elements).
We need to sum up to K, or just 0.
Because modulo is a natural number, the only way to get 0 is 0+0.
So we can have only 1 number of the form n = cK in our set.


For sum=K you need a = K-b
that means, if you choose `a', then `b' can't be present.


By instance, K=5
we can put all the numbers with modulo 1 or 2, leaving those with mod 3 or 4. You'll need to count them.
Don't forget to add the `5' itself