思路:

令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 ;
}

最新文章

  1. 如何去掉dede列表推荐时标题被加粗
  2. 走进AngularJs(三)自定义指令-----(上)
  3. JavaScript技巧[转载]
  4. phpcms get标签用法
  5. 树状DP (poj 2342)
  6. POJ Big Christmas Tree(最短的基础)
  7. vs2013安装visual assist和viemu之后提示功能等无效解决
  8. 2快速掌握OMD
  9. 1.4.2.4. SAVING(Core Data 应用程序实践指南)
  10. Java泛型类型擦除导致的类型转换问题
  11. console用法大全
  12. 利用docker搭建spark hadoop workbench
  13. hadoop集群篇--从0到1搭建hadoop集群
  14. Android基于JsBridge封装的高效带加载进度的WebView
  15. Chapter 1 Securing Your Server and Network(12):保护链接服务器
  16. vue 中如何对公共css、 js 方法进行单文件统一管理,全局调用
  17. 获取多个checkbox的选中值
  18. python-思路整理-虚拟环境
  19. go语言练习:指针
  20. 20155220 Exp5 MSF基础应用

热门文章

  1. BZOJ1926:[SDOI2010]粟粟的书架
  2. Happy Great BG-卡精度
  3. GBK点阵显示字库的制作和使用
  4. Docker入门(六):Stacks
  5. JavaScript高级程序设计学习笔记第五章--引用类型
  6. React-Redux之API
  7. linux私有ftp搭建与创建新用户
  8. vs2013错误 1 Unable to find messages file &#39;cscui.dll&#39;
  9. 《Java多线程编程核心技术》读后感(六)
  10. WP之样式