Long long ago in a far far away land there were two great cities and The Great Caravan Road between them. Many robber gangs “worked” on that road. By an old custom the i-th band robbed all merchants that dared to travel between ai and bi miles of The Great Caravan Road. The custom was old, but a clever one, as there were no two distinct i and j such that ai ≤ aj and bj ≤ bi. Still when intervals controlled by two gangs intersected, bloody fights erupted occasionally. Gang leaders decided to end those wars. They decided to assign each gang a new interval such that all new intervals do not intersect , for each gang their new interval is subinterval of the old one , and all new intervals are of equal length . You are hired to compute the maximal possible length of an interval that each gang would control after redistribution.
Long long ago in a far far away land there were two great cities and The Great Caravan Road between them. Many robber gangs “worked” on that road. By an old custom the i-th band robbed all merchants that dared to travel between ai and bi miles of The Great Caravan Road. The custom was old, but a clever one, as there were no two distinct i and j such that ai ≤ aj and bj ≤ bi. Still when intervals controlled by two gangs intersected, bloody fights erupted occasionally. Gang leaders decided to end those wars. They decided to assign each gang a new interval such that all new intervals do not intersect (to avoid bloodshed), for each gang their new interval is subinterval of the old one (to respect the old custom), and all new intervals are of equal length (to keep things fair). You are hired to compute the maximal possible length of an interval that each gang would control after redistribution.
标签： HBC54486爱吃素 质因数分解 素数判定 数论Caravan Robbers题解
