思路:
令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的更多相关文章
-
[ Codeforces Round #549 (Div. 2)][D. The Beatles][exgcd]
https://codeforces.com/contest/1143/problem/D D. The Beatles time limit per test 1 second memory lim ...
-
CF1143D/1142A The Beatles
CF1143D/1142A The Beatles 将题目中所给条件用同余方程表示,可得 \(s-1\equiv \pm a,s+l-1\equiv \pm b\mod k\). 于是可得 \(l\e ...
-
Let It Be - The Beatles - Lyrics
轉載自 https://www.youtube.com/watch?v=0714IbwC3HA When I find myself in times of trouble, Mother Mary ...
-
D. The Beatles
链接 [https://codeforces.com/contest/1143/problem/D] 题意 就是有nkcity,n个面包店 第一个面包店在1city,第x个在(x-1)k+1city ...
-
CodeForces #549 Div.2 D. The Beatles
题目 解题思路 关键是要 ,找出L 的组合,然后遍历L的组合,用最大公约数就可以算出来当前L的值要停多少次 怎么找出L的组合呢?饭店是每隔K 有一个,是重复的,我们只需要算出第一个饭店两侧,起点和停顿 ...
-
A-the Beatles
传送门: 题意:题目给出n,k分别代表在这个环中饭店的个数和两个饭店相离的距离.然后再给出一组a,b分别代表在某一点s里最近饭店的距离和在这个s点走一步之后到达的点离最近饭店的距离. 然后问这个人再次 ...
-
CF-1143D. The Beatles
题意:有间隔为k的n个点在数轴上,下标为 \(1,k+1, 2*k+1,\cdots (n-1)*k+1\) 首尾相接.设起点为s,步长为L,而现在只知道s距离最近的点的距离为a,和(s+L)距离最近 ...
-
『题解』Codeforces1142A The Beatles
更好的阅读体验 Portal Portal1: Codeforces Portal2: Luogu Description Recently a Golden Circle of Beetlovers ...
-
Entity Framework 6 Recipes 2nd Edition(13-10)译 ->; 显式创建代理
问题 你有一个POCO实体,原本在执行一个查询时动态创建代理,现在你不想EF延迟创建代理带来的代价. 解决方案 假设你有一个如图Figure13-15的模型 Figure 13-15. A model ...
随机推荐
-
Angular企业级开发-AngularJS1.x学习路径
博客目录 有链接的表明已经完成了,其他的正在建设中. 1.AngularJS简介 2.搭建Angular开发环境 3.Angular MVC实现 4.[Angular项目目录结构] 5.[SPA介绍] ...
-
jQuery Ready 与 Window onload 的区别(转)
“我们都知道,很多时候,在页面加载完后都需要做一些相应的初始化动作.例如,运行某些js特效,设置表单等等.怎么知道页面加载完了呢?一 般情况下都是设置body标签的onload监听window的loa ...
-
vector与set区别(基础知识)
首先,vector是序列式容器而set是关联式容器.set包含0个或多个不重复不排序的元素.也就是说set能够保证它里面所有的元素都是不重复的.另外对set容器进行插入时可以指定插入位置或者不指定插入 ...
-
Servlet小试
Java响应Http请求: 1.创建项目 因为对Java环境不是很熟悉,第一步卡住了好长时间, javax怎么引用, 在Java EE 5 Libraries中的javaee.jar中,项目中怎么引用 ...
-
此文件时入口文件index.php
此文件时入口文件index.php <?php //定义一下ThinkPHP框架存放的路径 define('THINK_PATH','./ThinkPHP/'); //定义当前的项目的名称,此处 ...
-
Python学习(二) 运行Python,编译Python
无论windos还是Linux只要安装了python,配置好了环境变量,则在命令行输入python这个命令的时候就会进入交互模式.在这个模式下可以进行一些简单的python代码编写.退出可以使用exi ...
-
浅谈C# 多态的魅力(虚方法,抽象,接口实现)
前言:我们都知道面向对象的三大特性:封装,继承,多态.封装和继承对于初学者而言比较好理解,但要理解多态,尤其是深入理解,初学者往往存在有很多困惑,为什么这样就可以?有时候感觉很不可思议,由此,面向对象 ...
-
实体类和数据表的映射异常(XXX is not mapping[ ])
在使用SSH框架开发过程,使用hibernate框架提供的工具类实现与数据库数据交互,在执行cmd操作时,如果出现以下异常: org.hibernate.hql.ast.QuerySyntaxExce ...
-
python+selenium十五:CSS与Jquery
在css中,id用#表示,class用.表示,要定位标签直接写标签名,其他属性就用[xxx='xxx'] 一.css定位 1.属性定位:可以通过任意属性定位,不局限于id.class.name.tag ...
-
BZOJ3110 [Zjoi2013]K大数查询 树套树 线段树 整体二分 树状数组
欢迎访问~原文出处——博客园-zhouzhendong 去博客园看该题解 题目传送门 - BZOJ3110 题意概括 有N个位置,M个操作.操作有两种,每次操作如果是1 a b c的形式表示在第a个位 ...