1. ned
My idea : enumrate
#include <bits/stdc++.h>
using namespace std;
const long long MOD=1000000009;
int main() {
int L;cin >> L;
long long A[L];
for (int i=0;i<L;i++) cin >> A[i];
long long P=1;
for (int i=0;i<L;i++) {
P*=A[i];
P%=MOD;
for (int j=i+1;j<L;j++) {
A[i] = __gcd(A[i], A[j]);
if (A[i]==1) break; // After Contest
P*=A[i];
P%=MOD;
}
}
cout << P;
return 0;
}
Optimizes :
When A_i = 1 , For any j \gt i , A_j = 1 , so you can break the loop now since the product P will not change. (Line 16)
With this optimization and constraint 2, you can get 40.
Complexity : O(n^2) (worst)
Full constraints :
