We have two arrays of integer with n elements ( n <= 10^5 ) , consider:

a1 a2 a3 ... an

b1 b2 b3 ... bn

( abs(a[i],b[i]) <= 10^9 )

print maximum first k element c=(a[i] * b[j]) ( 1<=i,j<=n)

For example: input: n=3 k=3

a={1,2,3}

b={4,5,6}

Correct output: 6 12 18

I'm trying to solve problem like this , but i don't have any idea for getting "AC" , so i need some helps , thank everybody.

Hi guys , i'm solving this problem:

For array a[i] with n elements ( 1 <= n <= 3000 , abs(a[i]) <= 10^9 )

Ask: After m loop ( 1 <= m <= 10^9 ) , print all of value in array a. Every loop , a[i]=a[i] + a[i-1] + ... + a[1]

Test input: 5 4 2 8 1 1 2

Test output: 4 10 24 39 55

Explain: loop1: 4 6 14 15 16 loop2: 4 10 24 39 55

My ideas was found formula math

I detects this:

For ex with n=5 , m=5 , in array a[5] , we have: loop1: a5 + a4 + a3 + a2 + a1

loop2: a5 + 2a4 + 3a3 + 4a2 + 5a1

loop3: a5 + 3a4 + 6a3 + 10a2 + 15a1

loop4: a5 + 4a4 + 10a3 + 20a2 + 35a1

loop5: a5 + 5a4 + 15a3 + 35a2 + 70a1

Look at this matrix , we are only care about the coefficent , so we have:

1 1 1 1 1

1 2 3 4 5

1 3 6 10 15

1 4 10 20 35

1 5 15 35 70

So the intiall problem change to the problem how to calcute quickly for function f(i)(j) , with:

f(1)(j) = 1 , f(i)(1) = 1

f(i)(j) = f(i-1)(j) + f(i)(j-1)

I can't find the formular for this function , so i need anybody helps me to find the formular or solve the intiall problem.

Thank you so much !

Hi guys! I'm trying to find an algorithm or idea for solving this problem:

For array a[] has n element ( 2 <= n <= 10^5 , 1 <= a[i] <= 1e5 ) , find one co-prime number in this array ( if it doesn't have any,print -1) , simply: Find (i;j) ( 1<= i < j <= n) so that gcd(a[i],a[j]) = 1 -> print a[i] and a[j].

Of course, the obvious solution would be to use Euclid's algorithm for each pair (ai, aj), but its pesimistic complexity is n(n+1)/2 times the complexity of Euclid's algorithm.

Is there a way to do that in O(n) or O(n*log(n)) or better ?

I find this post: https://stackoverflow.com/questions/26948793/finding-whether-there-are-two-coprime-numbers-in-an-array?fbclid=IwAR27s_3krUKgvYiZJg6MR2TnPreGrCNgkyIjnwlKVln_kIg20LZwykO2Glc

But it doesn't give what i need , so i hope anyone can help me.

Thank you!

Hi everyone, I'm wondering if people who often participate in competitions, who are qualified in competitive programming, how to debug bugs? By couting everything (C++), or using the codeblock's debug tool?