Untitled
c_cpp
2 months ago
3.0 kB
2
Indexable
Never
class Solution { public: const int MOD = 1e9 + 7; int arr[100001]; int ct [100001]; void primescore(){ memset(ct, 0, sizeof(ct)); for(int i=1; i<=100000; i++){ arr[i]=i; } ct[1]=0; for (int i = 2; i <= 100000; ++i) { if (arr[i]!= 1) { for (int j = i; j <=100000; j += i) { while(arr[j]%i==0){ arr[j]=arr[j]/i; } ct[j]++; } } } } long long binaryExponentiation(long long n, long long m) { long long result = 1; n %= MOD; while (m > 0) { if (m % 2 == 1) { result = (result * n) % MOD; } n = (n * n) % MOD; m /= 2; } return result; } int maximumScore(vector<int>& prisco, int k) { primescore(); int n =prisco.size(); vector<int>nums; for(int i=0; i<n; i++){ nums.push_back(ct[prisco[i]]); } vector<int>left, right; stack<int>st; for(int i=0; i<n; i++){ while(st.size() && nums[st.top()]<nums[i]){ st.pop(); } if(st.size()==0){ left.push_back(-1); }else { left.push_back(st.top()); } st.push(i); } while(st.size())st.pop(); for(int i=n-1; i>=0; i--){ while(st.size() && nums[st.top()]<=nums[i]){ st.pop(); } if(st.size()==0){ right.push_back(n); }else { right.push_back(st.top()); } st.push(i); } reverse(right.begin(), right.end()); while(st.size())st.pop(); // for(int i=0; i<n; i++){ // cout<<left[i]<<" "; // } // cout<<endl; // for(int j=0; j<n; j++){ // cout<<right[j]<<" "; // } // cout<<endl; vector<int>final; for(int i=0; i<n; i++){ final.push_back((right[i]-i)*(i-left[i])); // cout<<final[i]<<" "; } priority_queue<pair<int, int>>pq; for(int i=0; i<n; i++){ pq.push({prisco[i],final[i]}); } // cout<<endl; long long ans=1; while(k){ pair<int, int>front = pq.top(); pq.pop(); // cout<<front.first<<" "<<front.second<<endl; if(front.second<=k){ ans= (ans* binaryExponentiation(front.first, front.second))%MOD; k=k-front.second; }else{ ans= (ans* binaryExponentiation(front.first, k))%MOD; k=0; } } return ans; return 0; } };