Codeforces Beta Round #7 C. Line Exgcd
C. Line
题目连接:
http://www.codeforces.com/contest/7/problem/C
Description
A line on the plane is described by an equation Ax + By + C = 0. You are to find any point on this line, whose coordinates are integer numbers from - 5·1018 to 5·1018 inclusive, or to find out that such points do not exist.
Input
The first line contains three integers A, B and C ( - 2·109 ≤ A, B, C ≤ 2·109) — corresponding coefficients of the line equation. It is guaranteed that A2 + B2 > 0.
Output
Output the sequence of lines. Each line should contain either the result of alloc operation procession , or ILLEGAL_ERASE_ARGUMENT as a result of failed erase operation procession. Output lines should go in the same order in which the operations are processed. Successful procession of alloc operation should return integers, starting with 1, as the identifiers of the allocated blocks.
Sample Input
2 5 3
Sample Output
6 -3
Hint
题意
给你一条直线,让你找出直线上的一个整数点,不存在输出-1
题解:
exgcd裸题
求一下ax+by=gcd(a,b)的x,y之后,再check一下-c%gcd(a,b)是否等于0就好了,不等于0,那就输出-1
否则就怼一波。
代码
#include<bits/stdc++.h>
using namespace std;
void gcd(long long a,long long b,long long& d,long long& x,long long& y)
{
if(!b){d=a,x=1,y=0;}
else{gcd(b,a%b,d,y,x);y-=x*(a/b);}
}
int main()
{
long long a,b,c,d,x,y;
cin>>a>>b>>c;c=-c;
gcd(a,b,d,x,y);
if(c%d!=0)return puts("-1"),0;
else
{
printf("%lld %lld\n",x*c/d,y*c/d);
}
}
最新文章
- [leetcode] 题型整理之数字加减乘除乘方开根号组合数计算取余
- ASP.NET 开发必备知识点(2):那些年追过的ASP.NET权限管理
- spring 配置定时任务
- MaxMin搜索
- Contains Duplicate
- C# 连接SQL数据库
- JAVA多线程下,获取递增的序列号
- Coursera-Neural Networks by Geoffrey Hinton
- Qt5窗口设计
- eclipse luna 无法安装veloeclipse问题
- SpringMVC传参
- 201521123029《Java程序设计》第十一周学习总结
- Java读取excel表格
- echarts图表
- Python进程池Pool
- ElasticSearch 一
- Windows Server 2012更新补丁后导致Micosoft ODBC for Oracle出现问题
- Oracle通过ROWID删除表中重复记录
- 95% CI, 置信区间 Confidence Interval
- Hive格式各种格式下不同压缩算法的比较