CF1142A The Beatles

时间:2022-12-17 23:05:59

思路:

令p表示步数,l表示步长。由于p是使(l * p) % (n * k) == 0的最小的p,所以p = (n * k) / gcd(n * k, l).

设l = k * x + r,则由题意可知r有四种可能的取值,分别是(a + b) % k, ((-a + b) % k + k) % k, ((a - b) % k + k) % k, ((-a - b) % k + k) % k,枚举各种情况计算即可。

实现:

 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, k;
void solve(ll r, ll & minn, ll & maxn)
{
for (int x = r ? : ; k * x + r <= n * k; x++)
{
ll ans = n * k / __gcd(n * k, k * x + r);
minn = min(minn, ans);
maxn = max(maxn, ans);
}
}
int main()
{
ll a, b;
while (cin >> n >> k >> a >> b)
{
ll minn = INF, maxn = ;
solve((a + b) % k, minn, maxn);
solve(((-a + b) % k + k) % k, minn, maxn);
solve(((a - b) % k + k) % k, minn, maxn);
solve(((-a - b) % k + k) % k, minn, maxn);
cout << minn << " " << maxn << endl;
}
return ;
}

CF1142A The Beatles的更多相关文章

  1. &lbrack; Codeforces Round &num;549 &lpar;Div&period; 2&rpar;&rsqb;&lbrack;D&period; The Beatles&rsqb;&lbrack;exgcd&rsqb;

    https://codeforces.com/contest/1143/problem/D D. The Beatles time limit per test 1 second memory lim ...

  2. CF1143D&sol;1142A The Beatles

    CF1143D/1142A The Beatles 将题目中所给条件用同余方程表示,可得 \(s-1\equiv \pm a,s+l-1\equiv \pm b\mod k\). 于是可得 \(l\e ...

  3. Let It Be - The Beatles - Lyrics

    轉載自 https://www.youtube.com/watch?v=0714IbwC3HA When I find myself in times of trouble, Mother Mary ...

  4. D&period; The Beatles

    链接 [https://codeforces.com/contest/1143/problem/D] 题意 就是有nkcity,n个面包店 第一个面包店在1city,第x个在(x-1)k+1city ...

  5. CodeForces &num;549 Div&period;2 D&period; The Beatles

    题目 解题思路 关键是要 ,找出L 的组合,然后遍历L的组合,用最大公约数就可以算出来当前L的值要停多少次 怎么找出L的组合呢?饭店是每隔K 有一个,是重复的,我们只需要算出第一个饭店两侧,起点和停顿 ...

  6. A-the Beatles

    传送门: 题意:题目给出n,k分别代表在这个环中饭店的个数和两个饭店相离的距离.然后再给出一组a,b分别代表在某一点s里最近饭店的距离和在这个s点走一步之后到达的点离最近饭店的距离. 然后问这个人再次 ...

  7. CF-1143D&period; The Beatles

    题意:有间隔为k的n个点在数轴上,下标为 \(1,k+1, 2*k+1,\cdots (n-1)*k+1\) 首尾相接.设起点为s,步长为L,而现在只知道s距离最近的点的距离为a,和(s+L)距离最近 ...

  8. 『题解』Codeforces1142A The Beatles

    更好的阅读体验 Portal Portal1: Codeforces Portal2: Luogu Description Recently a Golden Circle of Beetlovers ...

  9. Entity Framework 6 Recipes 2nd Edition(13-10)译 -&gt&semi; 显式创建代理

    问题 你有一个POCO实体,原本在执行一个查询时动态创建代理,现在你不想EF延迟创建代理带来的代价. 解决方案 假设你有一个如图Figure13-15的模型 Figure 13-15. A model ...

随机推荐

  1. Angular企业级开发-AngularJS1&period;x学习路径

    博客目录 有链接的表明已经完成了,其他的正在建设中. 1.AngularJS简介 2.搭建Angular开发环境 3.Angular MVC实现 4.[Angular项目目录结构] 5.[SPA介绍] ...

  2. jQuery Ready 与 Window onload 的区别&lpar;转&rpar;

    “我们都知道,很多时候,在页面加载完后都需要做一些相应的初始化动作.例如,运行某些js特效,设置表单等等.怎么知道页面加载完了呢?一 般情况下都是设置body标签的onload监听window的loa ...

  3. vector与set区别&lpar;基础知识&rpar;

    首先,vector是序列式容器而set是关联式容器.set包含0个或多个不重复不排序的元素.也就是说set能够保证它里面所有的元素都是不重复的.另外对set容器进行插入时可以指定插入位置或者不指定插入 ...

  4. Servlet小试

    Java响应Http请求: 1.创建项目 因为对Java环境不是很熟悉,第一步卡住了好长时间, javax怎么引用, 在Java EE 5 Libraries中的javaee.jar中,项目中怎么引用 ...

  5. 此文件时入口文件index&period;php

    此文件时入口文件index.php <?php //定义一下ThinkPHP框架存放的路径 define('THINK_PATH','./ThinkPHP/'); //定义当前的项目的名称,此处 ...

  6. Python学习&lpar;二&rpar; 运行Python&comma;编译Python

    无论windos还是Linux只要安装了python,配置好了环境变量,则在命令行输入python这个命令的时候就会进入交互模式.在这个模式下可以进行一些简单的python代码编写.退出可以使用exi ...

  7. 浅谈C&num; 多态的魅力(虚方法,抽象,接口实现)

    前言:我们都知道面向对象的三大特性:封装,继承,多态.封装和继承对于初学者而言比较好理解,但要理解多态,尤其是深入理解,初学者往往存在有很多困惑,为什么这样就可以?有时候感觉很不可思议,由此,面向对象 ...

  8. 实体类和数据表的映射异常(XXX is not mapping&lbrack; &rsqb;)

    在使用SSH框架开发过程,使用hibernate框架提供的工具类实现与数据库数据交互,在执行cmd操作时,如果出现以下异常: org.hibernate.hql.ast.QuerySyntaxExce ...

  9. python&plus;selenium十五:CSS与Jquery

    在css中,id用#表示,class用.表示,要定位标签直接写标签名,其他属性就用[xxx='xxx'] 一.css定位 1.属性定位:可以通过任意属性定位,不局限于id.class.name.tag ...

  10. BZOJ3110 &lbrack;Zjoi2013&rsqb;K大数查询 树套树 线段树 整体二分 树状数组

    欢迎访问~原文出处——博客园-zhouzhendong 去博客园看该题解 题目传送门 - BZOJ3110 题意概括 有N个位置,M个操作.操作有两种,每次操作如果是1 a b c的形式表示在第a个位 ...