Codeforces Gym100812 L. Knights without Fear and Reproach-扩展欧几里得(exgcd)
补一篇以前的扩展欧几里得的题,发现以前写错了竟然也过了,可能数据水???
这个题还是很有意思的,和队友吵了两天,一边吵一边发现问题???
L. Knights without Fear and Reproach
http://codeforces.com/gym/100812/problem/L
2.0 s
256 MB
standard input
standard output
They were all dead. The final lunge was an exclamation mark to everything that had led to this point. I wiped my sword from the blood of Dragon and sheathed it. And then it was all over. Devastated, I came out of the empty castle and wandered somewhere along a dirt road. But before I could think about what I would do now, I heard a piercing scream from behind: "Stop right now! Drop a sword and raise your hands up!". They were knights. Only knights scream like that before making a hit. If they had been bandits I would be already dead.
I turned back and saw two figures in heavy armor rushing towards me. They were Lancelot and Percival — two knights of the Round Table, known for their fast reprisal over renegades like me. In the Kingdom they were called the Cleaners. As for me, not the most suitable name: they usually left a lot of dirt.
I almost instantly read their technique. Each of them was preparing for some time, then hit instantly, then was preparing again for the same time, then hit again, and so on, while their victim was not fallen. Lancelot spent n seconds to prepare, and Percival — m seconds. I was too tired and could parry a hit only if the previous one was done more than a second ago, and there were no powers to counter-attack at all. It was the sense that Lady Luck was really a hooker, and you were fresh out of cash. The knights knew their job and the first hit I wouldn't be able to parry would finish me off. My story wouldn't have a happy end.
The only line contains two integers separated by a space: n and m (1 ≤ n, m ≤ 2·109) — the intervals of time in seconds between hits of Lancelot and Percival correspondingly.
Output a single integer — the number of seconds from the beginning of the fight when the protagonist will be killed.
9 6
18
7 11
22
//L - Knights without Fear and Reproach-扩展欧几里得
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){ //扩展欧几里得
if(b==){
x=;y=;
return a;
}
ll r=exgcd(b,a%b,x,y);
ll t=y;
y=x-(a/b)*y;
x=t;
return r;
} int main(){
ll n,m,ans;
scanf("%lld%lld",&n,&m);
ll x,y;
ll c=exgcd(n,m,x,y);
if(n==&&m==)ans=;
else if(n==||m==)ans=; //特判
else{
if(c!=)
ans=n*m/c;
else{
if(n*m/c>max(abs(x*n),abs(y*m))){
ans=max(abs(x*n),abs(y*m));
if(ans==abs(x*n))ans=abs(((x+m)%m)*n);
else ans=abs(((y+n)%n)*m);
}
else
ans=n*m/c;
}
}
printf("%lld\n",ans);
}
溜了,去写别的题了。
最新文章
- shiro在springmvc里面的集成使用【转】
- js实现一个简单计算器
- C语言编译过程
- C# 代码编程规范
- 前向否定界定符 python正则表达式不匹配某个字符串 以及无捕获组和命名组(转)
- forever start Error: Cannot find module &#39;./daemon.v0.10.26&#39;
- PowerShell入门(一):PowerShell能干什么?
- C#调用存储过程实现分页(个人代码笔记)
- 一次失败的刷题经历:[LeetCode]292之尼姆游戏(Nim Game)(转)
- ionic/cordvoa 修改platform文件夹里的文件,build会覆盖问题
- Ubuntu下errno值
- CodeForces628-B.New Skateboard
- [学习笔记]Java代码中各种类型变量的内存分配机制
- CRM4.0 上传附件大小限制
- Java四中引用
- 【LOJ】#2567. 「APIO2016」划艇
- 001.RAID简介
- awk 脚本同时解析多个文件
- [py]多态的理解
- 修改Tomcat端口
热门文章
- openstack源
- V4L2学习(五)VIVI虚拟摄像头驱动
- 3224: Tyvj 1728 普通平衡树(finger tree)
- 33、secret
- [oldboy-django][3作业汇总]登录,注册最终版
- [oldboy-django][2深入django]django模板使用函数
- SQL SERVER存储引擎——04.数据
- Mysql,phpmyadmin密码忘了怎么办
- 【bzoj1146】[CTSC2008]网络管理Network 倍增LCA+dfs序+树状数组+主席树
- libcmt.lib和msvcrt.lib冲突,原因和解决方法