As an experiment the Educational Codeforces Round 33 will be rated for Div. 2. ×

Amit_Badshah's blog

By Amit_Badshah, history, 3 months ago, In English,

Can any one tell me the solution of the problem.

Eg. Input: 2 3 9 Output: 3 Explanation: Total sub-array are:- {2}, {3}, {9}, {2, 3}, {3, 9}, {2, 3, 9}

Subarray which violets the property are:- {9} -> {3 * 3}, Since 3 is a repeating prime factor in prime decomposition of 9 {3, 9} -> {3 * 3 * 3}, 3 is a repeating prime factor in prime decomposition of 27 {2, 3, 9} -> {2 * 3 * 3 * 3}, 3 is repeating prime factor in prime decomposition of 54 Hence total subarray remains which satisfies our condition are 3.

Input: 2, 3, 5, 15, 7, 2 Output: 12

 
 
 
 
  • Vote: I like it  
  • -9
  • Vote: I do not like it  

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use two pointers approach. We'll store array cnt, cnt[x] means count of prime factor x in our current subarray. So solution is O(Nsqrt(X)) or O(NlogX + X) depending on the way you'll factorize numbers.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it