Given an array of size N$N$ and two integers K$K$ and S$S$, the special sum of a subarray is defined as follows:

(Sum of all elements of the subarray) * (K$K$ - p$p$ * S$S$)

Where p$p$ = number of distinct prime factors of “product of all elements of the subarray”.

Find the maximum special sum by considering all non-empty subarrays of the given array.

-----Input-----
- First line contains 3 integers N$N$, K$K$ and S$S$.     
- Second line contains N$N$ integers, the elements of the array.  

-----Output-----
Output a single integer. The maximum special sum considering all non-empty subarrays of the array.

-----Constraints:-----
- 1≤N,K,S≤105$ 1 \leq N, K, S \leq 10^5 $ 
- 0≤K/S≤20$ 0 \leq K / S \leq 20 $ 
- 1<$ 1 < $ Any element of array <105$ < 10^5 $

-----Sample Input-----
4 10 2

14 2 7 15

-----Sample Output-----
138

-----Sample Explanation-----
Consider the subarray {14, 2, 7}

Total number of distinct prime factors in it is 2 (2 and 7).

Therefore, value of special sum is (14 + 2 + 7) * (10 - 2 * 2) = 138.

This is the subarray with the maximum special sum.

Source: codechef | Difficulty: VERY_HARD
Tags: Mathematics

Number theory

Implementation


Solutions:
from math import floor, sqrt
try:
	long
except NameError:
	long = int

def fac(n):
	(step, maxq, d) = (lambda x: 1 + (x << 2) - (x >> 1 << 1), long(floor(sqrt(n))), 1)
	q = n % 2 == 0 and 2 or 3
	while q <= maxq and n % q != 0:
		q = step(d)
		d += 1
	return q <= maxq and [q] + fac(n // q) or [n]
(n, k, s) = map(int, input().split())
(a, di, l, m, ans, su) = (list(map(int, input().split())), {}, [], 0, 0, 0)
for i in a:
	(bb, su) = (list(set(fac(i))), su + i)
	for j in bb:
		try:
			di[j] += 1
		except KeyError:
			(m, di[j]) = (m + 1, 1)
	l.append(su * (k - m * s))
	if su * (k - m * s) < 0:
		(m, di, su) = (0, {}, 0)
print(max(l))


from collections import defaultdict
lim = 100000
maxpf = 6
lpf = [2, 1] * (lim // 2 + 1)
lpf[2] = 1
k = 3
while k * k <= lim:
	if lpf[k] == 1:
		for m in range(k * k, lim, 2 * k):
			if lpf[m] == 1:
				lpf[m] = k
	k += 2

def nfacmax(arr, nfac):
	rpf = defaultdict(int)
	low = 0
	lowp = 0
	nmax = 0
	for a in arr:
		for f in a[1:]:
			rpf[f] += 1
		while len(rpf) > nfac:
			b = arr[low]
			for g in b[1:]:
				rpf[g] -= 1
				if rpf[g] == 0:
					del rpf[g]
			lowp = b[0]
			low += 1
		if len(rpf) == nfac:
			v = a[0] - lowp
			if v > nmax:
				nmax = v
	return nmax
(n, k, s) = map(int, input().split())
vs = list(([v] for v in map(int, input().split())))
posf = (k - 1) // s
minv = [lim + 1] * (maxpf + 1)
minf = maxpf + 1
cml = 0
for vi in vs:
	v = vi[0]
	cml += v
	vi[0] = cml
	red = v
	lf = 0
	while red > 1:
		f = lpf[red]
		if f == 1:
			(f, red) = (red, 1)
		else:
			red //= f
		if f > lf:
			vi.append(f)
		lf = f
	dpf = len(vi) - 1
	if dpf < minf:
		minf = dpf
	if v < minv[dpf]:
		minv[dpf] = v
if minf > posf:
	res = lim * s * maxpf
	for fc in range(minf, maxpf + 1):
		if minv[fc] <= lim:
			fres = (fc * s - k) * minv[fc]
			if fres < res:
				res = fres
	print(-res)
else:
	best = 0
	for f in range(minf, posf + 1):
		fmax = nfacmax(vs, f)
		if fmax * (k - f * s) > best:
			best = fmax * (k - f * s)
	print(best)


import numpy as np
import math
import os
import sys

def prime_factors(num):
	pf_set = set()
	while num % 2 == 0:
		pf_set.add(2)
		num = num / 2
		pass
	root = int(math.sqrt(num))
	for i in range(3, root + 1, 2):
		while num % i == 0:
			pf_set.add(i)
			num = num / i
	if num > 2:
		pf_set.add(num)
	return pf_set
(n, k, s) = list(map(int, input().split()))
in_arr = list(map(int, input().split()))
a = np.asarray(in_arr)
local_max = 0
global_max = -sys.maxsize
normal_sum = 0
lps = set()
for i in range(n):
	normal_sum = a[i] + normal_sum
	ps = prime_factors(a[i])
	p = ps.__len__()
	lps = ps.union(lps)
	lp = lps.__len__()
	sum_1 = a[i] * (k - p * s)
	sum_2 = normal_sum * (k - lp * s)
	if sum_1 > sum_2:
		local_max = sum_1
		lps = ps
		lp = p
		normal_sum = a[i]
	else:
		local_max = sum_2
	if local_max > global_max:
		global_max = local_max
		pass
	pass
print(global_max)