GCD Queries - Codeforces

→ Обратите внимание

До соревнования
Codeforces Round 940 (Div. 2) and CodeCraft-23
39:04:01
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя vidit_123

GCD Queries

Автор vidit_123, история, 7 лет назад, По-английски

Given an array,how to solve queries (10^5) of type Q:Value,L,R where value is a number and we need to report the count of all the numbers in the range [L,R] of the array such that gcd(Value,A[i])>1 where L<=i<=R. Given ARRAY SIZE :- 10^5 Each number 1<= A[i] <=10^5 TL = 1 Sec

primes, gcd, queries

vidit_123
7 лет назад
41

Комментарии (29)

Показать архивные | Написать комментарий?

radoslav11

7 лет назад, # |

+11

What are the constraints for the number of elements and the values (a_i)?

→ Ответить

tenshi_kanade

7 лет назад, # |

← Rev. 4 →

+27

I'd like to know more details (time limit, amount of numbers in array and constraints on the numbers), but anyway, I'll share the solution that came to mind.

No number up to 10⁹ has more than 1344 divisors, so we can find divisors of every element of array and store a list of positions that divide every number. This may or may not fit in memory or time, depending on the constraints. This step is $\text{[math]}$ , where M is the maximum value an array element can take.
Now for each query, make a list of the primes that divide Value. There are at most 9 such primes, because the product of the first 10 primes is $>10^9$. Now for every possible mask of primes, check how many positions of range [L, R] divide their product with a binary search and use inclusion-exclusion principle. This process is O(2⁹ * _logN) for each query, making the whole program O(Q * 2⁹ * _logN). This, again, may or may not fit in time depending on the constraints.

→ Ответить

vidit_123

7 лет назад, # ^ |

TL = 1 sec Array size is 10^5 And Each number is 1<=A[i]<=100000

→ Ответить

tenshi_kanade

7 лет назад, # ^ |

← Rev. 4 →

Then it should work. $\text{[math]}$ of the first step is OK for M ≤ 10⁵ is OK. Now the second step has less complexity because the number of prime factors is at most 6, so it's O(Q * 2⁶ * _logN), which is also OK.

Do you have an online judge where I can test the solution?

→ Ответить

vidit_123

7 лет назад, # ^ |

← Rev. 2 →

This was a subproblem of some other problem (tree based) .The link to the problem is https://www.codechef.com/problems/GTREE

→ Ответить

ABalobanov

7 лет назад, # ^ |

I think codechef problem is much easier than the one mentioned by you. Solution is similar but we can solve it without binary search just doing dfs and storing for each p how many numbers in current subtree are divisible by p.

→ Ответить

rock19

6 лет назад, # ^ |

← Rev. 2 →

-73

Can you explain this " store a list of positions that divide every number"?

→ Ответить

radoslav11

6 лет назад, # ^ |

+109

Maybe after the CodeChef xD

→ Ответить

rock19

6 лет назад, # ^ |

-7

Ok.No problem.

→ Ответить

TheeLooser

6 лет назад, # ^ |

← Rev. 4 →

-31

→ Ответить

stringray

6 лет назад, # ^ |

can u elaborate how you are doing the binary search to obtain count of elements in [L,R] which divisible a certain mask of primes?

→ Ответить

..vince

6 лет назад, # |

← Rev. 2 →

this problem is from codechef march long challange..

it still running dude, don't cheat

→ Ответить

Dalgerok

6 лет назад, # ^ |

+17

look when the blog was published :)

I think this is a problemsetter's codeforce account...

→ Ответить

rock19

6 лет назад, # ^ |

-27

Exactly.Thank you @Dalgerok.

→ Ответить

CodeChefFuckYou

6 лет назад, # |

-44

At first generate a list of primes that divide a number, for all number till M, the maximum number. This takes $\text{[math]}$ .

Now, for each number of the array a_i, lets say the primes p₁, p₂, ..., p_k divide that number, you can get this quickly from step 1. Go through all subsets of these primes. If a subset is p_i₁, p_i₂, ..., p_{i_r}, then insert i to list pos_{p_i₁·p_i₂... p_{i_r}}. This step takes O(2⁶n).

Now when you receive a query X, take the primes p₁, p₂, ..., p_k, that divides X, from the list generated at first. Now go through all of its subsets. Let the chosen subset be p_i₁, p_i₂, ..., p_{i_r}, then count how many times a number from [l, r] appears in pos_{p_i₁·p_i₂... p_{i_r}}. It can be done with two binary searches. If r is odd then add the count to answer, else subtract this count. It can be proven that this gives the answer, by inclusion-exclusion principal. Basically this counts number of numbers with at least one prime common with the query X. This step takes $\text{[math]}$

→ Ответить

TheeLooser

6 лет назад, # ^ |

-39

talk is cheap, send code

→ Ответить

CodeChefFuckYou

6 лет назад, # ^ |

-34

Which part you didn't understand?

→ Ответить

TheeLooser

6 лет назад, # ^ |

-44

talk is cheap, send code

→ Ответить

nater5247

6 лет назад, # ^ |

-35

Code is costly, spend time

→ Ответить

TheeLooser

6 лет назад, # ^ |

-47

o, really?

→ Ответить

CodeChefFuckYou

6 лет назад, # ^ |

-30

Ok, you can generate the list of prime divisors this way —

vector<int> div[M]; 

for(int i = 2; i < M; i++) { 
  if(div[i].size() == 0) { 
    for(int j = i; j < M; j += i) 
      div[j].push_back(i);
  }
}

As $\text{[math]}$ , this runs in $\text{[math]}$ .

→ Ответить

TheeLooser

6 лет назад, # ^ |

-32

talk is cheap, send full ACed code

→ Ответить

himkha_100

6 лет назад, # ^ |

← Rev. 2 →

-6

→ Ответить

Fekete

6 лет назад, # |

-7

Why are you upvoting this post? It is cheating, and this post should be deleted immediately, I think because it violates CodeChef rules and principles of the competitive programming.

→ Ответить

pleasant

6 лет назад, # ^ |

This blog post was created 6 months ago. However the current interest in this post can be attributed to CodeChef's problem.

→ Ответить

TooNewbie

6 лет назад, # ^ |

+23

This blog has nothing to do with CodeChef, the thing should be deleted is CodeChef problem. CodeChef should really care about problems of long challenge, because in 10 days even we can find code of problem from internet.

→ Ответить

Fekete

6 лет назад, # ^ |

Sorry, I missed this fact. So it's good that later comments are downvoted and unclarified.

→ Ответить

R2__D2

6 лет назад, # |

← Rev. 2 →

You also can do it with bitset. numbers less than 10^5 has less than 7 prime divisors. So for every primes less than 1e5 set the bit of positions of those numbers which are divided by.

GCD(x, a[i]) has no common prime divisors If their GCD is 1. you can travel through prime divisors and check how many numbers you can divide in the given range. then the ans might be (r-l+1- NumberofSetBit).

you can solve it easily than other technique.

→ Ответить

hmm

5 лет назад, # ^ |

-9

Can you please explain more on this line "So for every primes less than 1e5 set the bit of positions of those numbers which are divided by." If possible, please post the link to code of this approach.

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 20.04.2024 02:30:59 (f1).

Десктопная версия, переключиться на мобильную.

При поддержке