11392 - Binary*3 Type Multiple

[sclo]

I don't understand why my O(n) algorithm get TLE. Is there any faster way to solve it?

[rio]

I got AC with 2.65~ sec using O(n) algorithm.

-----
Rio

[tanaeem]

I have got AC in 1.960 sec.
My algorithm is order of no. of 3 (most obvious one)

[CMG]

O(n)? I don't see any relationship between the numbers and their answers, other than the fact that at some point when you reach an odd prime number that hasn't been used in the factors of the previous answers its answer will be p-1 p-1 0. What am I missing that makes this problem easy to calculate?

[rio]

Heres my approach:
For k=14, the answer is 3333330.

Code: Select all

3333330 = 3*(10^6+...+10^1)

14 does not have factor 3, so it means 10^6+...+10^1 is divisible by 14.

If k doesn't have factor 3, the problem is to find (a,b) such that 0<=a<=b and 10^b+10^(b-1)+...+10^a is divisible k.
This could be done by O(n) algorithm.
If k is divisible by 3, divide it by 3 and do the same thing.
-----
Rio

[sclo]

I did similar approach, except it doesn't matter if k is divisible by 3 or not. I basically compute 333...3 mod k for each length

[hamedv]

problem 10127 is another version of this problem. you can code it in less than 15 lines. in this problem numbers can be multiple of 2 or 5 because you can add zeros to the end of your number.

[crackerwang]

but i want to know is any num which can'ti div by 2 or 5 have a mutiple like 111..1111

[hamedv]

if a number is a multiple of 2 it's first digit must be 0 or 2 or 4 or 6 or 8.
and if a number is a multiple of 5 it's first digit must be 0 or 5.
due this a number which is like this "11..11" is not a multiple of 2 or 5.

[fh]

Can somebody check whether my output is correct?
Or is there any tricky input?

Code: Select all

Input:

1
2
3
4
5
6
7
8
9
10
11
12
13
236773
42610
207363
428950
718729
958356
227092
63702
922718
84511
298077
803248
249764
882133
249776
858939
723076
244080
954760
335073

Code: Select all

Output:

1 1 0
2 1 1
1 1 0
3 1 2
2 1 1
2 1 1
6 6 0
4 1 3
3 3 0
2 1 1
2 2 0
3 1 2
6 6 0
39462 39462 0
4261 4260 1
2652 2652 0
2048 2046 2
16206 16206 0
11408 11406 2
14195 14193 2
10615 10614 1
230680 230679 1
12072 12072 0
22926 22926 0
8224 8220 4
7346 7344 2
126018 126018 0
7660 7656 4
11792 11792 0
2757 2755 2
1012 1008 4
23871 23868 3
3660 3660 0

[rio]

My AC code got same output as yours.

-----
Rio

[fh]

The problem is to find (a,b) such that 0<=a<=b and 10^b+10^(b-1)+...+10^a is divisible k.
This could be done by O(n) algorithm.

My algo is O(L + K) where L is the length of the multiple in the output. K iteration is needed to initalize the array. I use GCD in each iteration of L. I got TLE. How to better than this?

[greve]

First of all it suffices to look at the numbers 3,33,333, 3333 etc., since any number ending in some number of 0s can be expressed as the difference of two of these numbers with no 0s, ie. 333 - 33 = 300.

Hint: If you start marking the remainders you get mod K from this sequence, what happens when you get a remainder that you have seen before (and why does this prove that a solution always exists)?

[fh]

First of all it suffices to look at the numbers 3,33,333, 3333 etc., since any number ending in some number of 0s can be expressed as the difference of two of these numbers with no 0s, ie. 333 - 33 = 300.

Hint: If you start marking the remainders you get mod K from this sequence, what happens when you get a remainder that you have seen before (and why does this prove that a solution always exists)?

Awesome.. I never thought of this elegant solution. Thanks greve

[f74956227]

Hi! I got AC within 2.XX sec by O(n), but i see that there are someone who got AC within only 1 sec
is there a O(1) algorithm ??