这题要掌握同余一个非常关键的性质： a c ≡ b c ( m o d p ) ac\equiv bc(mod\ p) ac≡bc(mod p)可以转化为 a ≡ b ( m o d p g c d ( p , c ) ) a\equiv b(mod\ {p\over gcd(p, c)}) a≡b(mod gcd(p,c)p)。
那么分析题目，容易得到如下同余式：
( y − 1 ) d + x ≡ ( x − 1 ) d + y ( m o d w ) , 1 ≤ x < y ≤ m i n ( m , d ) (y-1)d+x\equiv (x-1)d+y(mod\ w),1\le x < y \le min(m, d) (y−1)d+x≡(x−1)d+y(mod w),1≤x<y≤min(m,d)
移项，
( y − x ) ( d − 1 ) ≡ 0 ( m o d w ) (y-x)(d-1)\equiv 0(mod\ w) (y−x)(d−1)≡0(mod w)
这时套用最上面给出的公式得到 y − x ≡ 0 ( m o d w g c d ( w , d − 1 ) ) y-x\equiv 0(mod \ {w\over gcd(w,d-1)}) y−x≡0(mod gcd(w,d−1)w)
下面记 p = w g c d ( w , d − 1 ) , u p = m i n ( m , d ) p={w\over gcd(w,d-1)},up=min(m,d) p=gcd(w,d−1)w,up=min(m,d)。
那么我们就是要找到在 [ 1 , u p ] [1,up] [1,up]区间内所有 y − x y-x y−x是 p p p的倍数的整数对 ( x , y ) ( x < y ) (x,y)(x<y) (x,y)(x<y)。
最简单的想法就是枚举 y − x y-x y−x，从 p p p枚举到 c n t = ⌊ u p p ⌋ cnt=\lfloor {up\over p}\rfloor cnt=⌊pup⌋。
那么答案就是 Σ i = 1 c n t ( u p − p i ) \Sigma_{i=1}^{cnt}(up-pi) Σi=1cnt(up−pi)，化简一下之后变成 c n t ∗ u p − p ( 1 + c n t ) c n t / 2 cnt*up-p(1+cnt)cnt/2 cnt∗up−p(1+cnt)cnt/2， O ( 1 ) O(1) O(1)即可求得答案。
算上之前的 g c d gcd gcd，复杂度为 O ( l o g ( n ) ) O(log(n)) O(log(n))。
做的时候推到最后一步不会求对数了。实际上没理解到 x , y x,y x,y的取值范围是固定的，知道取值范围不变之后就非常好做了。
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int t; cin >> t; while (t--) { ll m, d, w; cin >> m >> d >> w; ll p = w / __gcd(w, d - 1); ll up = min(m, d), cnt = up / p; cout << up * cnt - p * (1 + cnt) * cnt / 2 << endl; } return 0; }实际上就是在给的 n n n个数里面找有没有出现和下面的 w w w个数一样的形状。
那么做个差分跑一遍KMP就完了。
注意特判 w = 1 w=1 w=1。
复杂度 O ( n + m ) O(n+m) O(n+m)
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int n, w; cin >> n >> w; if (w == 1) cout << n << endl; else { vector <int> a(n), b(w); vector <int> da(n), db(w); for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 0; i < w; ++i) cin >> b[i]; for (int i = 1; i < n; ++i) da[i] = a[i] - a[i - 1]; for (int i = 1; i < w; ++i) db[i] = b[i] - b[i - 1]; vector <int> nxt(w, 0); for (int i = 2, j = 0; i < w; ++i) { while (j > 0 && db[j + 1] != db[i]) j = nxt[j]; if (db[j + 1] == db[i]) ++j; nxt[i] = j; } int cnt = 0; for (int i = 1, j = 0; i < n; ++i) { while (j > 0 && db[j + 1] != da[i]) j = nxt[j]; if (db[j + 1] == da[i]) ++j; if (j == w - 1) ++cnt, j = nxt[j]; } cout << cnt << endl; } return 0; }