hdu 2669(扩展欧几里得)
2024-09-29 06:26:31
Romantic
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4400 Accepted Submission(s): 1852
Problem Description
The Sky is Sprite.
The Birds is Fly in the Sky.
The Wind is Wonderful.
Blew Throw the Trees
Trees are Shaking, Leaves are Falling.
Lovers Walk passing, and so are You.
................................Write in English class by yifenfei
The Birds is Fly in the Sky.
The Wind is Wonderful.
Blew Throw the Trees
Trees are Shaking, Leaves are Falling.
Lovers Walk passing, and so are You.
................................Write in English class by yifenfei
Girls are clever and bright. In HDU every girl like math. Every girl like to solve math problem!
Now
tell you two nonnegative integer a and b. Find the nonnegative integer X
and integer Y to satisfy X*a + Y*b = 1. If no such answer print "sorry"
instead.
Input
The input contains multiple test cases.
Each case two nonnegative integer a,b (0<a, b<=2^31)
Each case two nonnegative integer a,b (0<a, b<=2^31)
Output
output
nonnegative integer X and integer Y, if there are more answers than the
X smaller one will be choosed. If no answer put "sorry" instead.
nonnegative integer X and integer Y, if there are more answers than the
X smaller one will be choosed. If no answer put "sorry" instead.
Sample Input
77 51
10 44
34 79
10 44
34 79
Sample Output
2 -3
sorry
7 -3
sorry
7 -3
题解:由ax+by = gcd(a,b) 当 a,b互素是才会有解。然后X要是尽量小的正数,假设我们得到的是 X0 ,在有解的情况下方程ax+by=c的通解为 {X0*(c/d)+k*b/gcd(a,b)} (k = ..-2,-1,0,1,2..)
所以我们可以得到在最小的X为 (X0%b+b)%b.代入得Y
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long LL; LL extend_gcd(LL a,LL b,LL &x,LL &y){
if(!b){
x=,y = ;
return a;
}else{
LL x1,y1;
LL d = extend_gcd(b,a%b,x1,y1);
x = y1;
y = x1 - a/b*y1;
return d;
}
}
int main()
{
LL a,b,x,y;
while(~scanf("%lld%lld",&a,&b)){
LL d = extend_gcd(a,b,x,y);
if(d!=){
printf("sorry\n");
}else{
x = (x%b+b)%b;
y = (-a*x)/b;
printf("%lld %lld\n",x,y);
}
}
return ;
}
最新文章
- PropertyGrid控件由浅入深(一):文章大纲
- finnal 评论 II
- FIRST集和FOLLOW集
- careercup-位操作5.1
- WP e-Commerce WordPress Payment Gateways Caller插件本地文件包含漏洞
- hdu 5159 Card (期望)
- NYOJ10,skiing
- CMap与hash_map效率对照
- javascript实现页面滚屏效果
- ubuntu 15.10 安装jdk
- MVC使用jQuery从视图向控制器传递Model,数据验证,MVC HTML辅助方法小结
- linux下主机用户管理(完整详情)
- windows 命令相关
- NOIP2018游记(划掉) 滚粗记
- AI-CBV写法
- php 允许浏览器跨域访问web服务端的解决方案
- ASP.NET MVC:Form Authentication 相关的学习资源
- Linux的shell script
- Spring Boot系列教程二:创建第一个web工程 hello world
- 【期望DP】BZOJ3450- Tyvj1952 Easy
热门文章
- 笔记1 python入门学习笔记
- datetime模块详解
- poj2955:Brackets
- S变换
- loj2045 「CQOI2016」密钥破解
- 使用WMI Filter 实现组策略的筛选!
- Android 使用intent传递返回值:startActivityForResult()与onActivityResult()与setResult()参数分析,activity带参数的返回
- Python+Selenium练习篇之21-如何截图并保存
- 从shell(终端)中退出python
- Visual C++ 经典的人脸识别算法源代码