• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

Problem

传送门:左转右转

Solution

至高无上的xxx250说这道题有循环节,且观察样例可大胆猜测周期一定是\(AB\)的因数。

题目要求求这一坨玩意:

\[\begin{cases}

x=((t \ l floor \ frac { t } { B } \ r floor)\ \ B mod A \ \

y=(t\ \bmod B)

\end{cases}\]

设循环节为\(k\),因为\(t=0\)时,\(\begin{cases} x=0 \\

y=0

\end{cases}\),所以,\(\begin{cases}

x=((k \frac{k}{B})\ \bmod A)=0\\

y=(k \ \bmod B)=0

\end{cases}\)

即\(\begin{cases}

0=(k \frac{k}{B}) \ \bmod A \\

0=(k \ \ B模式b)

\end{cases}\)

因为\(0=(k \ \bmod B)\)所以式子中的向下取整可以去掉0=(k \frac{k}{B}) \ \bmod A\)于是可化为\(0=\frac{k(B 1)}{B} \ \bmod A\)

所以\(0 \ equiv \ frac { k(B 1)} { B } \ \ B mod A \)

式子可化为\(0 \ equiv \ frac { k } { B } \(\ bmod \ \ frac { A } { gcd(A,B 1)})\)

移项可得\(0 \ equiv k \(\ bmod \ \ frac { AB } { gcd(A,B 1)})\)

所以最小循环节为\(k(\bmod \ \frac{AB}{gcd(A,B 1)})=0\),所以\(k=\frac{AB}{gcd(A,B 1)}\)

然后题目所求可以转化为区间覆盖问题。

分类讨论亿一下,区间\([l,r]\)

若\(k \leq r - l 1\),则答案为\(k\)

否则,设\(L=l \bmod k,R=r \bmod k\)。将点对映射到数轴上,将其转化为一个线段覆盖问题。(需要分别考虑\(L \leq R\)和\(长R\)的情况)

\(代码:\)

//最小循环节线段覆盖

#includebits/stdc .h

使用命名空间标准

typedef long long ll

const int MAX _ N=1000000 5;

int n,m;

洛杉矶、英国、韩国

结构节点{

ll l,r;

} s[MAX _ N];

内嵌布尔cmp(节点一,节点b){

返回一磅。l;

}

int main(){

scanf('%d%lld%lld ',n,A,B);

k=A/__gcd(A,B1)* B;

如果(k0)k=2e 18;

for(int I=1;I=n;i){

ll l,r;

scanf('%lld%lld ',l,r);

if(r-l 1=k){

ans=k;

继续;

}

否则{

l%=k,r %=k;

if(lr) s[ m]=(node){0,r},s[ m]=(node){l,k-1 };

else s[ m]=(node){l,r };

}

}

如果(答案){

printf('%lld\n ',ans);

返回0;

}

sort(s 1,s 1 m,CMP);

ans=0;

ll L=s[1].l,R=s[1].r;

s[ m]=(node){k,k };

for(int I=2;I=m;i){

if(Rs).l){

ans=R-L 1;

L=s.l,R=s.r;

}

否则{

R=max(s).R,R);

}

}

printf('%lld\n ',ans);

返回0;

}

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now