Wuyanru's blog
0%

[SNOI2019] 数论

发表于 分类于 ，

前几天我们 NOIP 模拟赛的最后一题，然后一不小心挂了 分，痛失 ak。

题目链接：luoguP5330。

题意

给定两个数 和两个集合 。

求 。

题解

首先我们来看一个显而易见的规律：

假如说 。

我们会发现，数字对于 取模的值构成了“循环”，并且所有这些循环，对答案的贡献是相同的。

这些循环的答案非常容易计算，并且我们还可以知道一个循环的大小为 。

这就是当 为 公倍数时的解法。

配合暴力，我们可以拿到 分。

现在我们可以快速处理一个完整的循环，但是如果最后数字的个数不足以构成循环，我们就只能暴力。

显然，这样时间复杂度是 的。

我们再来找规律，把数字 的值做成表格。

vik4Mj.png

vik5ss.png

发现什么了吗？

对于第一个表格， 的数字分别是 ，这些数字 的值分别是 。

的数字分别是 ，这些数字 的值分别是 。

有没有发现什么？

再看一眼第二个表格。

的数字分别是

的值分别是 。

的数字分别是

的值分别是 。

发现了什么呢？

假如说上一个出现的数字 的值是 ，那么下一个值就是 。

好，现在让我们把这个序列写出来，但是这个序列中可能不包含 中的所有数，所以我们把若干个这样的序列“拼”在一起。

举个例子，对于第二个表格，对应的序列就是 ，对于第一个表格，对应的序列就是 。

然后呢？不难发现，对于某一个 的值，他对答案的贡献在这个序列中是完整的一段。

然后前缀和就可以了。

前缀和维护的是 的这个排列中，前 个数字里面，有多少个属于集合 。

所以可以直接枚举 中的元素，计算它的贡献。

我考场上傻了，写了个线段树。

时间复杂度 。

我写的是 。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// DABC ABCD ABCA DBAA
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;
using pi=pair<int,int>;
using ll=long long;
using pl=pair<ll,ll>;
using pli=pair<ll,int>;
template<typename A>
using vc=vector<A>;
using vi=vector<int>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int gcd(int a,int b)
{
    int r=a%b;
    while(r)
    {
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}
bool pp[1000001];
bool qq[1000001];
int t1[4000001];
int val[1000001];
int wh[1000001];
int visa[1000001];
int visb[1000001];
int a[1000001];
int b[1000001];
int n,m,p,q;
int tot;
ll ans;
ll t;
void add(int p,int pl,int pr,int x)
{
    t1[p]++;
    if(pl==pr) return ;
    int mid=(pl+pr)>>1;
    if(x<=mid) add(p*2,pl,mid,x);
    else add(p*2|1,mid+1,pr,x);
}
int get(int p,int pl,int pr,int l,int r)
{
    if(l<=pl&&pr<=r) return t1[p];
    int mid=(pl+pr)>>1,ans=0;
    if(l<=mid) ans+=get(p*2,pl,mid,l,r);
    if(mid<r) ans+=get(p*2|1,mid+1,pr,l,r);
    return ans;
}
int main()
{
    p=read(),q=read(),n=read(),m=read(),t=lread();
    int num=gcd(p,q);ll round=(ll)p*q/num;
    for(int i=1;i<=n;i++) a[i]=read(),visa[a[i]%num]++,pp[a[i]]=1;
    for(int i=1;i<=m;i++) b[i]=read(),visb[b[i]%num]++,qq[b[i]]=1;
    for(int i=0;i<num;i++) ans+=(ll)visa[i]*visb[i]*(t/round);
    ll rest=t-(t/round)*round;
    for(int i=0;i<num;i++)
    {
        for(int j=i;;)
        {
            val[++tot]=j;
            wh[j]=tot;
            j=(j+p)%q;
            if(j==i) break;
        }
    }
    // for(int i=1;i<=q;i++) printf("%d ",val[i]);
    // printf("\n");
    for(int i=1;i<=m;i++) add(1,1,q,wh[b[i]]);
    for(int i=1;i<=n;i++)
    {
        int v=a[i];//第v行
        if(rest<i) continue;
        int step=rest/p;
        if(v<rest%p) step++;
        if(!step) continue;
        int l=wh[v%q],r=wh[v%q]+step-1;
        // printf("%d : %d %d ",a[i],l,r);
        l--,r--;
        // ll mem=ans;
        if(l/(q/num)==r/(q/num)) ans+=get(1,1,q,l+1,r+1);
        else
        {
            int l2=l/(q/num)*(q/num);
            int r2=l2+q/num-1;
            ans+=get(1,1,q,l2+1,r-(q/num)+1);
            ans+=get(1,1,q,l+1,r2+1);
            // printf("%d %d %d %d ",l2+1,r-(q/num)+1,l,r2);
        }
        // printf("%lld\n",ans-mem);
    }
    printf("%lld\n",ans);
    return 0;
}

感谢观看！