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