呼叫版主，貌似是数学题 - C语言论坛

第 11 楼

得分:0

被好几道给卡了

第 12 楼

得分:0

这题的难度比我想象的要大，至今没有好的方法。置顶以博得高手的关注，希望能看到精彩的算法出现。

重剑无锋，大巧不工

第 13 楼

得分:0

没人。。。。。。

第 14 楼

得分:0

重赏之下必有勇夫。

第一个完成该题目的人（AC），贴上来代码，我奖励1000专家分。

重剑无锋，大巧不工

第 15 楼

得分:0

上不了贵校OJ，不知道能不能AC，而且由于是晚自习后回宿舍才看到这题，明天又要参加数学建模要早睡，所以有错误的话，请多担待

由题可知，子矩阵和可视为a和b两个数组两个区间和的积，分别称为sa和sb，那么c所有的因子都在sa和sb里
因为c很小，因子不到100个，所以可以直接枚举sa包含哪个因子，那么sb就包含剩下的
设sa能被t1整除，则sb应被t2=c/t1整除。这里可以分别统计a模t1的前缀和，设suma[i]表示(a[0]+...+a[i])%t1，若suma[i]=suma[j]且j<i，说明a[j+1]+...+a[i]能整除t1，也就是找到了一个sa。我们可以统计值为suma[i]的元素有几个，那么遍历一遍就能找到所有sa，sb同理。
要注意的是，对于能整除t1的t1`，找到的sa有一部分也在计算t1时找到了，也就是会重复计算，要去重
代码如下：

程序代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define SE second
#define FI first
#define MP(x,y) make_pair(x,y)
const int MAXN = 30010;
const int MAXM = 110;
const int MOD = 1000000007;
const int INF =1000000007;
int sa[MAXN];
int arr[MAXN],brr[MAXN],suma[MAXN],sumb[MAXN],cnta[MAXN],cntb[MAXN];
pair<int,int> pa[MAXM];
long long cal(int a,int b,int n,int m)
{
    int tmpsa=0;
    long long bnum=0;
    for(int i=a;i<MAXN;i+=a)
        tmpsa-=sa[i];
    memset(cnta,0,sizeof(cnta));
    memset(cntb,0,sizeof(cntb));
    suma[0]=arr[0]%a;
    for(int i=1;i<n;++i)
        suma[i]=(suma[i-1]+arr[i])%a;
    sumb[0]=brr[0]%b;
    for(int i=1;i<m;++i)
        sumb[i]=(sumb[i-1]+brr[i])%b;
    cntb[0]=1;
    for(int i=0;i<m;++i)
        bnum+=cntb[sumb[i]]++;
    cnta[0]=1;
    for(int i=0;i<n;++i)
        tmpsa+=(cnta[suma[i]]++);
    if(sa[a]==0)
        sa[a]=tmpsa;
    return bnum*tmpsa;
}
int main()
{
    int ncase,n,m,c,ptop;
    long long ans;
    scanf("%d",&ncase);
    while(ncase--)
    {
        ans=0;
        ptop=0;
        memset(sa,0,sizeof(sa));
        scanf("%d%d%d",&n,&m,&c);
        for(int i=0;i<n;++i)
            scanf("%d",&arr[i]);
        for(int i=0;i<m;++i)
            scanf("%d",&brr[i]);
        for(int i=1;i*i<=c;++i)
            if(c%i==0)
            {
                ans+=cal(c/i,i,n,m);
                pa[ptop++]=MP(c/i,i);
            }
        for(int i=0;i<ptop;++i)
            ans+=cal(pa[i].SE,pa[i].FI,n,m);
        cout<<ans<<"\n";
    }
    return 0;
}