P5444 [APIO2019]奇怪装置

矫情吗；* 2021-10-19 19:36 215阅读 0赞

[传送门][Link 1]

考虑求出最小的循环节 $G$ 使得 $t,t+G$ 得到的数对是一样的

由 $y \\equiv t \\mod B$ ，得到 $G$ 一定是 $B$ 的倍数，设 $zB=G$，则 $t,t+zB$ 结果相同

代入 $x \\equiv (t+\\left \\lfloor \\frac\{t\}\{B\} \\right \\rfloor) \\mod A$

得到

$(t+zB+\\left \\lfloor \\frac\{t+zB\}\{B\} \\right \\rfloor) \\equiv (t+\\left \\lfloor \\frac\{t\}\{B\} \\right \\rfloor) \\mod A$

$(t+zB+z+\\left \\lfloor \\frac\{t\}\{B\} \\right \\rfloor) \\equiv (t+\\left \\lfloor \\frac\{t\}\{B\} \\right \\rfloor) \\mod A$

$(zB+z) \\equiv 0 \\mod A$

$z(B+1) \\equiv 0 \\mod A$

即 $z(B+1)$ 是 $A$ 的倍数

想得到最小的 $G$ 就要先求出最小的 $z$，考虑两边提出公因数 $\\gcd(A,B+1)$

那么 $z(B+1)/\\gcd(A,B+1) = kA/\\gcd(A,B+1) $

此时因为 $(B+1)/\\gcd(A,B+1)$ 已经和 $A/\\gcd(A,B+1)$ 没有公因数了

那么 $z$ 一定得是 $A/\\gcd(A,B+1)$ 的倍数，那么最小的 $z$ 就是当 $k=1$ 时， $z=A/\\gcd(A,B+1)$

所以 $G=zB=AB/gcd(A,B+1)$

那么对于一个时间段 $l,r$ ，如果 $r-l+1>=G$ 则所有数都会被覆盖到，答案就是 $G$

否则把 $l,r$ 对 $G$ 取模，因为此时 $r-l+1<G$，所以取模后如果 $l<=r$ 则 $l,r$ 区间的数会被考虑到

如果 $l>r$ 则 $\[0,r\]$ 和 $\[l,G-1\]$ 的数会被覆盖到，直接离散化看看哪些区间被覆盖到就好了

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    inline ll read()
    {
        ll x=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
        return x*f;
    }
    const int N=4e6+7;
    ll n,A,B,ans;
    ll gcd(ll a,ll b) { return b ? gcd(b,a%b) : a; }
    struct dat{
        ll pos,v;
        inline bool operator < (const dat &tmp) const {
            return pos!=tmp.pos ? pos<tmp.pos : v>tmp.v;
        }
    }d[N];
    ll tot;
    int main()
    {
        n=read(),A=read(),B=read();
        ll G=A/gcd(A,B+1)*B,l,r;//注意先除后乘
        while(n--)
        {
            l=read(),r=read();
            if(r-l+1>=G) { printf("%lld\n",G); return 0; }
            l=l%G,r=r%G;
            if(l<=r) d[++tot]=(dat){l,1},d[++tot]=(dat){r,-1};
            else d[++tot]=(dat){
        0,1},d[++tot]=(dat){r,-1},d[++tot]=(dat){l,1},d[++tot]=(dat){G-1,-1};
        }
        sort(d+1,d+tot+1); int now=0; ll pre;
        for(int i=1;i<=tot;i++)
        {
            if(d[i].v&&!now) pre=d[i].pos;//如果覆盖开始则记录左端点
            now+=d[i].v;
            if(!now) ans+=d[i].pos-pre+1;//覆盖结束统计答案
        }
        printf("%lld\n",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/LLTYYC/p/11355926.html

[Link 1]: https://www.luogu.org/problem/P5444