-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
111 lines (102 loc) · 2.62 KB
/
Solution.cs
File metadata and controls
111 lines (102 loc) · 2.62 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
public class Solution
{
int modulo = 1000000007;
public int MaximumScore(IList<int> nums, int k)
{
int[] spf = BuildSpf(100_000);
int n = nums.Count;
int[] primeScore = new int[n];
Number[] sortedNums = new Number[n];
for (int i = 0; i < n; i++)
{
primeScore[i] = GetPrimeScore(nums[i], spf);
sortedNums[i] = new Number(nums[i], i);
}
Array.Sort(sortedNums, (a, b) => b.value - a.value);
long score = 1;
int idx = 0;
long remain = k;
while (remain > 0)
{
Number best = sortedNums[idx];
long count = CountSubArrays(primeScore, best.index);
score = score * FastPower(best.value, Math.Min(remain, count)) % modulo;
idx++;
remain -= count;
}
return (int)score;
}
public record Number(int value, int index);
// Sieve Prime Factorization
int[] BuildSpf(int maxValue)
{
int[] spf = new int[maxValue + 1];
for (int i = 2; i <= maxValue; i++) spf[i] = i;
for (int i = 2; i <= maxValue; i++)
{
if (spf[i] == i)
{
for (int j = 2 * i; j <= maxValue; j += i)
{
if (spf[j] == j) spf[j] = i;
}
}
}
return spf;
}
int GetPrimeScore(int num, int[] spf)
{
HashSet<int> factors = [];
while (num > 1)
{
int prime = spf[num];
factors.Add(prime);
num /= prime;
}
return factors.Count;
}
long CountSubArrays(int[] primeScore, int curr)
{
int lastIndex = curr;
for (int i = curr; i < primeScore.Length; i++)
{
if (primeScore[i] <= primeScore[curr])
{
lastIndex = i;
}
else
{
break;
}
}
int firstIndex = curr;
for (int i = curr - 1; i >= 0; i--)
{
if (primeScore[i] < primeScore[curr])
{
firstIndex = i;
}
else
{
break;
}
}
int left = curr - firstIndex + 1;
int right = lastIndex - curr + 1;
return 1L * left * right;
}
public long FastPower(long a, long b)
{
long ans = 1;
while (b > 0)
{
if ((b & 1) > 0)
{
ans = ans * a % modulo;
}
a = a * a % modulo;
b >>= 1;
}
return ans;
}
}