正解:数论

解题报告:

我好像当初考的时候这题爆零了,,,部分分都没想到,,,我真的好菜$kk$

考虑如果在$t_1,t_2$两个时刻有$x_1=x_2,y_1=y_2$是什么情况$QwQ$?

那就有$\begin{cases}t_1+[\frac{t_1}{B}]\equiv t_2+[\frac{t_2}{B}](\mod A)\\t_1\equiv t_2(\mod B)\end{cases}$.

不妨设$t_2=t_1+B\cdot t$,代入得$t_1+[\frac{t_1}{B}]\equiv t_1+B\cdot k+[\frac{t_1+B\cdot k}{B}](\mod A)$,即$k(B+1)\equiv 0(\mod A)$

解得$\frac{A}{gcd(A,B+1)}|k$.即将$mod\ B$相等的提出来,发现每$\frac{A}{gcd(A,B+1)}$一循环.又因为$mod\ B$的结果有$B$个,所以总的循环节长度为$len=\frac{A\cdot B}{gcd(A,B+1)}$.

所以把$l,r$取模后变成若干条线段,然后现在询问$[0,len)$覆盖了多少个点.昂这个不差分下就行了嘛,$over$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define fi first

#define sc second

#define ll long long

#define gc getchar()

#define mp make_pair

#define P pair<ll,ll>

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ll i=x;i<=y;++i)

#define my(i,x,y) for(ll i=x;i>=y;--i)

const int N=1e6+;

const ll inf=1e18;

ll n,A,B,len,l[N],r[N],sum,dat,lst,as;

multiset<P>S;

il ll read()

{

    rc ch=gc;ll x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

il void ad(ll x,ll y){S.insert(mp(x,-));S.insert(mp(y,));}

int main()

{

    //freopen("5444.in","r",stdin);freopen("5444.out","w",stdout);

    n=read();A=read();B=read();len=A/gcd(A,B+)*B;rp(i,,n){l[i]=read(),r[i]=read();sum+=r[i]-l[i]+;}

    if(A/gcd(A,B+)>inf/B)return printf("%lld\n",sum),;

    rp(i,,n)

    {

        if(r[i]-l[i]>=len)return printf("%lld\n",len),;;//printf("l=%lld r=%lld len=%lld\n",r[i],l[i],len);

        if(l[i]/len!=r[i]/len)ad(l[i]%len,len-),ad(,r[i]%len);else ad(l[i]%len,r[i]%len);

    }

    multiset<P>::iterator it=S.begin();

    while(it!=S.end()){P tmp=*it;if(!dat)lst=tmp.fi;dat-=tmp.sc;if(!dat)as+=tmp.fi-lst+;++it;}

    printf("%lld\n",as);

    return ;

}

巴特西

洛谷$P5444\ [APIO2019]$奇怪装置数论

正解:数论

解题报告:

最新文章

热门文章

巴特西

洛谷$P5444\ [APIO2019]$奇怪装置 数论

正解:数论

解题报告:

最新文章

热门文章

洛谷$P5444\ [APIO2019]$奇怪装置数论