写一下这道题的类欧部分。

$$y\equiv kx\pmod p$$

这个方程在 $x,y\in[1,n\bmod p]$ 的范围内的整数解的个数便是题解所说的 $c_k$。记 $m=n\bmod p$。

也就是说 $kx-y=tp$ 其中 $t$ 为整数。不难发现，有多少个合法的 $t$ 就有多少个合法的整数解。

对于一个 $t$ 其合法的充分必要条件是 $kx-tp\in[1,m]$。注意到 $kx\equiv 0\pmod p$ 不成立。所以一个 $t$ 合法当且仅当 $kx-m\le tp\le kx$。也就是说 $t$ 满足 $\lceil\frac{kx-m}{p}\rceil\le t\le \lfloor\frac{kx}{p}\rfloor$。注意到对于固定的 $x$ 这个区间左右区间至多差 1。

所以我们将对于固定的 $x$ 的 $t$ 的数量表示为 $\lfloor\frac{kx}{p}\rfloor-\lceil\frac{kx-m}{p}\rceil+1$。 所以 $c_k=\sum\limits_{x=1}^m \lfloor\frac{kx}{p}\rfloor-\lceil\frac{kx-m}{p}\rceil+1$。我们将这个难看的上取整去掉。

$$\lceil\frac{a}{p}\rceil=\lfloor\frac{a}{p}\rfloor+1-[p|a] $$

带入上式 $c_k=\sum\limits_{x=1}^m \lfloor\frac{kx}{p}\rfloor-\sum\limits_{x=1}^m\lfloor\frac{kx-m}{p}\rfloor+[k^{-1}m\bmod p\le m]$。

很显然这个是 $\sum\limits_{x=0}^n\lfloor\frac{ax+b}{c}\rfloor$ 的类欧几里得的板子了。

记住：不要写unordered_map的记忆化，不写记忆化也可以随便跑。

提供一个这题用的类欧的板子。

long long f(int a,int b,int c,int n) {
	if(!a)return 1ll*b/c*(n+1);
//	unsigned long long has=gethas(a,b,c,n);
//	if(mem.find(has)!=mem.end())return mem[has];
	if(a>=c||b>=c)return /*mem[has]=*/1ll*(1ll*n*(n+1)/2)
	*(a/c)+1ll*(n+1)*(b/c)+f(a%c,b%c,c,n);long long m=(1ll*a*n+b)/c;
	return /*mem[has]=*/1ll*n*m-f(c,c-b-1,a,m-1);
}