Super Subarray Gym - 101498G（枚举+思维）

题目链接：https://vjudge.net/problem/Gym-101498G

**题目：**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.

Input
The 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 array a1, a2, …, an (1 ≤ ai ≤ 109), ai is the i-th element of the array a.

Output
For each test case, print a single integer that represents the number of Super Subarrays in a, on a single line.

Example
Input
2
5
1 2 3 4 5
5
2 3 4 3 6
Output
6
6

题意：输入n个数，求有多少个超级子串，当连续子串中所有数的和能 整除子串中的每一个数，那么这个字串为超级字串。

思路：既然求是否能整除每一个数，就可以转化求子串里这些数的最小公倍数，然后看子串中所有数的和是否能整除它们的最小公倍数即可。 可以直接枚举所有的子串，当它们的最小公倍数大于题目中给的最大的所有数之和（2e12）就跳出循环，详情见代码解析。

代码：

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <string>

using namespace std;

const long long inf =2e12;
const int maxn =2000+5;

long long a[maxn],sum[maxn];

long long gcd(long long x,long long y)
{
    if(y==0) return x;
    else return(gcd(y,x%y));

}

int main()
{
    int T,n;
    long long lcm,add_sum,ans,flag;

    scanf("%d",&T);
    while(T--)
    {
        ans=0;
        scanf("%d",&n);
        sum[0]=0;
        lcm=1;

        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }

        for(int i=1; i<=n; i++)
        {
            add_sum=a[i];
            lcm=a[i];
            for(int j=i; j<=n; j++)
            {
                if(i==j)
                {
                    ans++;
                    continue;
                }
                add_sum+=a[j];
                flag=lcm/gcd(lcm,a[j]);//当前的最小公倍数lcm=flag*a[j]，a[j]先不乘，以防爆数据

                if(a[j]>inf/flag)   //最小公倍数lcm=flag*a[j],这样判断就防止了爆数据
                break;//最小公倍数大于inf了
                else
                {
                    lcm=flag*a[j];
                    if(add_sum%lcm==0)
                        ans++;
                }

            }
        }
        printf("%lldn",ans);
    }
    return 0;
}

最后

以上就是风趣山水为你收集整理的Super Subarray Gym - 101498G（枚举+思维）的全部内容，希望文章能够帮你解决Super Subarray Gym - 101498G（枚举+思维）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。