帮直线数一数有多少点被它压在身下吧~

cheng2010 · 2026-02-01 21:10:01 · 算法·理论

有时候直线在数轴上扑到了很多点，但太多了~

而我们又想知道，它吧多少点压住了，怎么办呢~

类欧几里得

学了这个其实就差不多了。

part1 基础

万恶之源追根溯源，我们想要解决这个问题：

注意到若 a,b 有大于 c 的，则：

于是 a,b 都小于 c 了，然后就是推。。。接下来令 M=\lfloor \frac{an+b}{c} \rfloor

注意到最终的式子很像欧几里得算法辗转相减法，故得名类欧几里得，所以复杂度就是 O(\log N)。

然后就是一些扩展：

类似的推导，以 g 为例，以下默认 a,b\le c。

其他都是类似的，于是我们可以总结出式子了。

先回顾一下定义：

最终，我们得到了：

别担心，被吓哭是正常的。

其实仔细思考一下还是比较容易理解的。

发现可以一起递归求出 f,g,h，故得到了模板题的代码。

:::success[code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Mod=998244353,inv2=499122177,inv6=166374059;
struct Node{int f,g,h;}ans;
inline int sqr(int x){return 1ll*x*x%Mod;}
inline Node asgcd(int n,int a,int b,int c)
{
    Node res;
    int mul=n*(n+1)%Mod*inv2%Mod; 
    int a_c=a/c;
    int b_c=b/c;
    if(!a)
    {
        res.f=b_c*(n+1)%Mod;
        res.g=sqr(b_c)*(n+1)%Mod;
        res.h=mul*b_c%Mod;
    }
    else if(a>=c||b>=c)
    {
        Node calc=asgcd(n,a%c,b%c,c);
        res.f=(calc.f+mul*a_c+b_c*(n+1))%Mod;
        res.g=(calc.g+2*a_c*calc.h+2*b_c*calc.f+n*(n+1)%Mod*(n*2+1)%Mod*inv6%Mod*sqr(a_c)+n*(n+1)%Mod*a_c%Mod*b_c+(n+1)*sqr(b_c))%Mod;
        res.h=(calc.h+a_c*n%Mod*(n+1)%Mod*(n*2+1)%Mod*inv6+mul*b_c)%Mod;
    }
    else
    {
        int m=(a*n+b)/c;
        Node calc=asgcd(m-1,c,c-b-1,a);
        res.f=(n*m-calc.f+Mod)%Mod;
        res.g=((n*m%Mod*(m+1)-2*(calc.h+calc.f)-res.f)%Mod+Mod)%Mod;
        res.h=((m*n%Mod*(n+1)-calc.g-calc.f)%Mod+Mod)*inv2%Mod;
    }
    return res;
}
int n,a,b,c;
inline void solve()
{
    cin>>n>>a>>b>>c;
    ans=asgcd(n,a,b,c);
    cout<<ans.f<<' '<<ans.g<<' '<<ans.h<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
}

:::

然后看看 loj 上的模板吧。

求：

其中 k_1+k_2 \le 10。

有点麻烦，没有关系，其实是一样的。

接下来就是带入了。

把后面的拎出来：

终于！

于是就解决了，虽然套路，但挺复杂的。

:::success[code] 实现比较垃圾，是直接记忆化而不是一起递归，跑得比较慢。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Mod=1e9+7;
inline int ks(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res=res*a%Mod;
        a=a*a%Mod;
        b>>=1;
    }
    return res;
}
int B[22],fac[22],ifac[22],inv[22],C[22][22];
inline int getpw(int n,int k)
{
    if(!k)return n+1;
    int res=0,pw=n;
    for(int i=1;i<=k+1;i++)
    {
        (res+=C[k+1][i]*B[k+1-i]%Mod*pw)%=Mod;
        if(i<=k)(pw*=n)%=Mod;
    }
    return res*inv[k+1]%Mod;
}
struct Hash
{
    size_t operator()(const array<long long,6>&a)const noexcept
    {
        size_t h=0;
        for(auto x:a)
            h^=hash<long long>{}(x+0x9e3779b97f4a7c15ULL+(h<<6)+(h>>2));
        return h;
    }
};
unordered_map<array<int,6>,int,Hash> mp;
inline int calc(int n,int a,int b,int c,int k1,int k2)
{
    if(!k2)return getpw(n,k1);
    if(!a)return ks(b/c,k2)*getpw(n,k1)%Mod;
    array<long long,6> key={n,a,b,c,k1,k2};
    if(mp.count(key))return mp[key];
    if(a>=c||b>=c)
    {
        int res=0;
        int nB=ks(b/c,Mod-2);
        int M=ks(b/c,k2);
        for(int x=0;x<=k2;x++)
        {
            int mA=1;
            int mB=M;
            for(int y=0;y<=k2-x;y++)
            {
                if(y!=k2-x)
                {
                    (res+=calc(n,a%c,b%c,c,k1+y,x)*mA%Mod*mB%Mod*ifac[x]%Mod*ifac[y]%Mod*ifac[k2-x-y])%=Mod;
                    (mA*=(a/c))%=Mod,(mB*=nB)%=Mod; 
                }
                else
                {
                    (res+=calc(n,a%c,b%c,c,k1+y,x)*mA%Mod*ifac[x]%Mod*ifac[y])%=Mod;
                }
            }
            if(x!=k2)(M*=nB)%=Mod;
        }
        return mp[key]=res*fac[k2]%Mod;
    }
    int m=(a*n+b)/c;
    int res=(getpw(m,k2-1)-(k2==1))*getpw(n,k1)%Mod;
    for(int i=0;i<=k2-1;i++)
    {
        for(int j=1;j<=k1+1;j++)
            res=(res-calc(m-1,c,c-b-1,a,i,j)*C[k2-1][i]%Mod*B[k1+1-j]%Mod*inv[k1+1]%Mod*C[k1+1][j]%Mod+Mod)%Mod;
        if(!k1)
            res=(res-C[k2-1][i]*getpw(m-1,i)%Mod+Mod)%Mod;
    }
    (res*=k2)%=Mod;
    for(int i=1;i<=k2-1;i++)
        res=(res+Mod-B[k2-i]*C[k2][i]%Mod*calc(n,a,b,c,k1,i)%Mod)%Mod;
    return mp[key]=res;
}
inline void solve()
{
    int n,a,b,c,k1,k2;
    cin>>n>>a>>b>>c>>k1>>k2;
    cout<<calc(n,a,b,c,k1,k2)<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    mp.reserve(1<<20);
    mp.max_load_factor(0.7);
    C[0][0]=1;
    for(int i=1;i<=21;i++)
    {
        C[i][0]=1;
        for(int j=1;j<=21;j++)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%Mod;
    }
    B[0]=fac[0]=fac[1]=ifac[0]=ifac[1]=inv[0]=inv[1]=1;
    for(int i=2;i<=21;i++)
        fac[i]=fac[i-1]*i%Mod,
        ifac[i]=ks(fac[i],Mod-2),
        inv[i]=inv[Mod%i]*(Mod-Mod/i)%Mod;
    for(int i=1;i<=20;i++)
    {
        for(int j=0;j<i;j++)
            (B[i]+=B[j]*C[i+1][j])%=Mod;
        (B[i]*=inv[i+1])%=Mod;
        B[i]=(Mod-B[i])%Mod;
    }
    for(int i=1,opt=Mod-1;i<=20;i++,opt=Mod-opt)
        (B[i]*=opt)%=Mod;
    int T;cin>>T;
    while(T--)solve();
}

:::

part2 应用

显然但是，题目不会只是模板，需要转换。

Example1

link

给定 N,M,A,B ，求出：

\sum_{i=0}^{N}[(Ak+B) \bmod M>k]

:::success[solution] 先转换为 X_k \le k 的形式。

考虑利用 a \bmod b=a-b\lfloor \frac{a}{b} \rfloor，将原式变成 k(A-1)+B -1 < M \lfloor \frac{kA+B}{M} \rfloor。

将 M 除过去，于是变成了 \lfloor \frac{k(A-1)+B-1}{M} \rfloor < \lfloor \frac{kA+B}{M} \rfloor，然后让左边 +1，变成 \lfloor \frac{k(A-1)+B-1+M}{M} \rfloor \le \lfloor \frac{kA+B}{M} \rfloor

注意到左式减右式一定 \le 1，于是答案就是 \displaystyle \sum_{i=0}^{N-1} \lfloor \frac{k(A-1)+B+M-1}{M} \rfloor-\lfloor \frac{kA+B}{M} \rfloor 了。

这是经典的类欧的形式，直接做就好了，注意特判 A=0 的情况，为 \min(n,B)。 :::

由上例可看出，可以将某种计数转化为两个式子相减为 1 的形式，可以使用类欧。

Example2

link

给定正整数 n,\,r ，求：

:::success[solution] 看到向下取整，想到 floor sum，但是指数太可怕了吧。

考虑 (-1)^x 的性质，有 (-1)^{2x}=1，可以得到 (-1)^x=1-2(x \bmod 2)，化简一下可以得到：

带入 x=\lfloor d\sqrt{r} \rfloor 可得：

化简一下得到：

接下来，令 \displaystyle f(N,a,b,c)=\sum_{i=1}^{N} \lfloor \frac{ a\sqrt{r}+b}{c} i\rfloor，于是答案就是 n-2f(N,1,0,1)+4f(N,1,0,2)。

现在，开始推吧！

为了方便，令 t=\frac{ a \sqrt r+b}{c}。

正常的类欧是取模，但这怎么取模？考虑按 t 的大小来分类。

• part1：t \ge 1

考虑令 \delta=\lfloor t \rfloor，得到：

于是有：

• part2：t < 1

回忆之前的推导过程，我们令 M=\lfloor Nt \rfloor，带入可得：

因为此时 \lfloor it \rfloor 一定小于 it，所以这样写没有问题。

然后，推吧！

代码是简单的。

:::

Example3

有时会稍微考一考建模，比如下面这道题。

link

有 N 个编号为 1 到 N 的盘子。第 i 个盘子上有 a_i 个石子。此外，还有一个空袋子。
你可以按照任意顺序、任意次数（包括 0 次）进行以下两种操作：

• 从所有至少有 1 个石子的盘子中各取出 1 个石子，并将这些石子放入袋子中。
• 从袋子中取出 N 个石子，并将每个盘子上各放 1 个石子。仅当袋子中至少有 N 个石子时，才能进行此操作。

操作结束后，第 i 个盘子上的石子数为 b_i。请计算所有可能的长度为 N 的整数序列 (b_1,\ b_2,\ \dots,\ b_N) 的种数，并对 998244353 取模。

:::success[sulotion] 考虑我们能够到达一个怎么样的局面。

注意到我们一定是先进行若干次第一种操作，再进行若干次第二种操作，故可以先枚举先经行了多少次第一种操作，成为步骤 A。

注意到，如果两个步骤 A 和 A'，满足它们操作完的局面不同，那么容易证明，它们经过若干次全局加后的局面还是不同的，于是可以先把 a 排序，对于每个数它在前面的数全部减成 0 时被减了多少，可以得到式子：

其中 sum 是前缀和，(n-i+1)(j+a_{i-1})+sum_{i-1} 就是一共放入袋子多少球。

然后 floor sum 即可。 :::

万能欧几里得

不用推那些屎式子，除了常数大几乎没有缺点了。

而且顾名思义，作用范围很更广，万能！

因为更抽象，所以更强。

我们用 (N,a,b,c) 表示一条线段 y=\frac{ax+b}{c}(0< x \le N)，然后考虑一个由 U,R 构成的，长度为 N+\lfloor \frac{aN+b}{c} \rfloor 的字符串 S，满足有 N 个 U 和 \lfloor \frac{aN+b}{c} \rfloor 个 R，第 i 个 R 的前方有 \lfloor \frac{ai+b}{c} \rfloor 个 U。

几何解释就是从原点开始，每向右穿过一次竖向的网格线，就写下一个 R，每向上穿过一次横向的网格线，就写下一个 U。

用一下 oiwiki 的图就是：

注意不能有格外的 U 且要在开始时写下 \lfloor \frac{b}{c} \rfloor 个 U，并在经过整点时先写 U 再写 R。

我们将这样的 S 成为操作序列。

那么这有什么用？

考虑将 U,R 视作某个幺半群（存在单位元的半群）内的的元素，然后将整个操作序列视为幺半群内元素的乘积，而问题最终的答案与这个乘积有关，接下来我们用 \circ 表示这个幺半群的运算，e 表示单位元。

还是有点抽象，就以经典的式子：

为例吧。

初始有 cnt=0。

每遇到一个 U，就 cnt\leftarrow cnt+1，遇到一个 R，就 ans\leftarrow cnt \times i，其中 i 是这是第几个 R，最后 ans 就是答案。

我们用 f(S) 来表示 S 答案，注意到有 f(S_1+S_2)=f(S_1) \circ f(S_2)。

发现最终答案只 f(U),f(R) 有关，于是我们定义 F(n,a,b,c,f_1,f_2) 为求 \displaystyle \sum_{i=1}^{N} i\lfloor \frac{ai+b}{c} \rfloor，当前状态为 f_1，f_2 时的答案，其中 f_1 是更新答案状态，f_2 是用来更新答案的状态。

我们就要来求 F(n,a,b,c,f(U),f(R))。

首先，平移整格答案是不会变的，所以 b 可以任意对 c，考虑 a 对 c 取模的影响，发现是每个 R 的前面多了 \lfloor \frac{a}{c} \rfloor 的 U，所以可以得到：

接下来，还是令 M=\lfloor \frac{an+b}{c} \rfloor。

如果 M=0，则字符串全是 R 了，就直接就是 f_2^{N}。

否则考虑翻转这条直线，让其以 y=x 对称过去，原来斜率 <1，翻转后自然就 >1 了，可以继续递归。

考虑翻转的影响，将翻转的直线分成三段，分别为 \le 1 的部分，\le M 的部分和 >M 的部分。