思路：前缀和+哈希+容斥

推荐一道力扣题：连续的子数组和

上面这道题是判断是否存在连续子数组的和为$k$的倍数。在求出前缀和数组(设为$pre$)后，如果存在$i,j(i\lt j)$使$pre[i]mod\space k ==pre[j]mod\space k$,说明$pre[j]-pre[i]$是$k$的倍数。（消去了模$k$剩下的余数）

那么仿照该题思路，要同时是$3$和$5$的倍数，即同时是$15$的倍数。而同时也不是$4$的倍数，即不是$60$的倍数。并用哈希来计算统计前缀和在$mod\space 15$和$mod\space 60$的个数即可。

代码

C++

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn=1e5+10;
int n;
int nums[maxn];
ll ans=0;

int solve() {
    ll sum = 0;
    ll tmp15 = 0;
    ll tmp60 = 0;
    unordered_map<int, int> map15,map60;// Hash
    // 初始存在和为0的哈希值
    map15[0] = 1;
    map60[0] = 1;
    for (int i = 0; i < n; i++) {
        sum += nums[i];
            tmp15 = sum % 15;
            tmp60 = sum % 60;
        if (map15.find(tmp15) != map15.end()) {// 存在15的倍数
                ans += map15[tmp15];
                if(map60.find(tmp60) != map60.end()){// 存在60的倍数，需要减去
                        ans -= map60[tmp60];
                        }
        }
                map15[tmp15]++;
                map60[tmp60]++;
    }
}

int main(){
        scanf("%d",&n);
        for(int i=0;i<n;++i) scanf("%d",&nums[i]);
        solve();
        cout<<ans;
        
        return 0;
}

题目描述

小红有一个数组，他想知道有多少连续子数组的和同时是3和5的倍数，但不是4的倍数。

输入描述

第一行输入一个整数 $n(1\le n\le 10^5)$表示数组长度。 第二行输入$n$个整数表示数组 $a_i(1\le a_i\le 10^9)$

输出描述

一个整数。

样例

输入

3
13 17 30

输出

2