G - Super Subarray
In this problem, subarray is defined as non-empty sequence of consecutive elements.
We define a subarray as Super Subarray if the summation of all elements in the subarray is divisible by each element in it.
Given an array a of size n, print the number of Super Subarrays in a.
InputThe first line of the input contains a single integer T (1 ≤ T ≤ 100), the number of test cases.
The first line of each test case contains one integer n (1 ≤ n ≤ 2000), the length of array a.
The second line of each test case contains the sequence of elements of the arraya1, a2, ..., an (1 ≤ ai ≤ 109), ai is the i-th element of the array a.
OutputFor each test case, print a single integer that represents the number of Super Subarrays in a, on a single line.
Example Input 251 2 3 4 552 3 4 3 6 Output 66题意：给出n个数，问这n个数能组成多少种子串，满足子串的和能被子串中所有的元素整除。
分析：因为要所有元素被整除，所有很容易想到求lcm（最小公倍数），然后判断子串的和是否能被lcm整除。如果直接做，三层for会TLE，所以我们先用sum[i]数组处理前缀和，然后两层for即可，中间判断lcm是否大于了子串和的最大值（2000*1e9），大于则直接break。
代码如下： #include <map>#include <cmath>#include <queue>#include <stack>#include <vector>#include <cstdio>#include <string>#include <cstring>#include <iostream>#include <algorithm>#define LL long longusing namespace std;const int MX = 2e3 + 5;const int mod = 1e9 + 7;const int INF = 2e9 + 5;const LL maxn = 2000*1e9;LL a[MX], sum[MX];LL gcd(LL a, LL b){ return b == 0 ? a : gcd(b, a % b);}LL lcm(LL a, LL b){ return a/gcd(a, b)*b;}int main(){ int t, n; scanf("%d", &t); while(t--){ scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%I64d", &a[i]); } sum[0] = 0; for(int i = 1; i <= n; i++){ sum[i] = sum[i-1] + a[i]; } LL ans = 0; for(int i = 1; i <= n; i++){ LL tmp = a[i]; for(int j = i; j <= n; j++){ tmp = lcm(tmp, a[j]); if(tmp > maxn) break; if((sum[j] - sum[i-1]) % tmp == 0) ans++; } } printf("%I64dn", ans); } return 0;}
In this problem, subarray is defined as non-empty sequence of consecutive elements.
We define a subarray as Super Subarray if the summation of all elements in the subarray is divisible by each element in it.
Given an array a of size n, print the number of Super Subarrays in a.
InputThe first line of the input contains a single integer T (1 ≤ T ≤ 100), the number of test cases.
The first line of each test case contains one integer n (1 ≤ n ≤ 2000), the length of array a.
The second line of each test case contains the sequence of elements of the arraya1, a2, ..., an (1 ≤ ai ≤ 109), ai is the i-th element of the array a.
OutputFor each test case, print a single integer that represents the number of Super Subarrays in a, on a single line.
Example Input 251 2 3 4 552 3 4 3 6 Output 66