UVA 10673 扩展欧几里得

时间:2021-11-13 09:23:06

题意:给出x 和k,求解p和q使得等式x = p[x / k] + q [ x / k], 两个[x / k]分别为向下取整和向上取整

题解:扩展欧几里得

//meek///#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <sstream>
#include <vector>
using namespace std ;
#define mem(a) memset(a,0,sizeof(a))
#define pb push_back
#define fi first
#define se second
#define MP make_pair
typedef long long ll; const int N = ;
const int inf = ;
const int mod= ; ll ExpGcd(ll a,ll b,ll &x,ll &y)
{
ll temp,p;
if(b==)
{
x=; y=;
return a;
}
p=ExpGcd(b,a%b,x,y);
temp=x; x=y; y=temp-(a/b)*y;
return p;
} int main() {
int T;
scanf("%d",&T);
while(T--) {
ll x,k,X,Y;
scanf("%lld%lld",&x,&k);
ll a = floor(1.0*x/k);
ll b = ceil(1.0*x/k);
ll d = ExpGcd(a,b,X,Y);
//cout<<X<<" "<<Y<<endl;
//if(X<0) X=(X%b+b)%b;
X *= x/d;
Y *= x/d;
printf("%lld %lld\n",X,Y);
}
return ;
}

UVA 10673 扩展欧几里得的更多相关文章

  1. UVA 12169 Disgruntled Judge 扩展欧几里得

    /** 题目:UVA 12169 Disgruntled Judge 链接:https://vjudge.net/problem/UVA-12169 题意:原题 思路: a,b范围都在10000以内. ...

  2. UVA 12169 Disgruntled Judge 枚举&plus;扩展欧几里得

    题目大意:有3个整数 x[1], a, b 满足递推式x[i]=(a*x[i-1]+b)mod 10001.由这个递推式计算出了长度为2T的数列,现在要求输入x[1],x[3],......x[2T- ...

  3. UVA 10090 Marbles 扩展欧几里得

    来源:http://www.cnblogs.com/zxhl/p/5106678.html 大致题意:给你n个球,给你两种盒子.第一种盒子每个盒子c1美元,可以恰好装n1个球:第二种盒子每个盒子c2元 ...

  4. UVA 10090 Marbles(扩展欧几里得)

    Marbles Input: standard input Output: standard output I have some (say, n) marbles (small glass ball ...

  5. UVa 11768 格点判定(扩展欧几里得求线段整点)

    https://vjudge.net/problem/UVA-11768 题意: 给定两个点A(x1,y1)和B(x2,y2),均为0.1的整数倍.统计选段AB穿过多少个整点. 思路: 做了这道题之后 ...

  6. Intel Code Challenge Final Round &lpar;Div&period; 1 &plus; Div&period; 2&comma; Combined&rpar; C&period;Ray Tracing &lpar;模拟或扩展欧几里得&rpar;

    http://codeforces.com/contest/724/problem/C 题目大意: 在一个n*m的盒子里,从(0,0)射出一条每秒位移为(1,1)的射线,遵从反射定律,给出k个点,求射 ...

  7. POJ 1061 青蛙的约会 扩展欧几里得

    扩展欧几里得模板套一下就A了,不过要注意刚好整除的时候,代码中有注释 #include <iostream> #include <cstdio> #include <cs ...

  8. 【64测试20161112】【Catalan数】【数论】【扩展欧几里得】【逆】

    Problem: n个人(偶数)排队,排两行,每一行的身高依次递增,且第二行的人的身高大于对应的第一行的人,问有多少种方案.mod 1e9+9 Solution: 这道题由1,2,5,14 应该想到C ...

  9. poj 2891 扩展欧几里得迭代解同余方程组

    Reference: http://www.cnblogs.com/ka200812/archive/2011/09/02/2164404.html 之前说过中国剩余定理传统解法的条件是m[i]两两互 ...

随机推荐

  1. javascript中的原型和继承

    javascript一直是初学者口中的难点,甚至一些有些许工作经验的人也不太明白其中的原理,而我就是那个初学者,前段时间在阮一峰老师的博客上看了一篇文章<javascript继承机制的设计思想& ...

  2. ScrollView嵌套RecyclerView时滑动出现的卡顿

    原文连接:http://zhanglu0574.blog.163.com/blog/static/113651073201641853532259/   现象: 一个界面有多个RecyclerView ...

  3. Redis3&period;0&period;1 Stable版本的集群部署(Mac)

    本文档基于如下原始文档(CentOS)创建: http://blog.csdn.net/xu470438000/article/details/42971091 修改了一些路径的错误,补全了一些命令执 ...

  4. &lbrack;转载&rsqb;赖勇浩:推荐《Linux 多线程服务器端编程》

    推荐<Linux 多线程服务器端编程> 赖勇浩(http://laiyonghao.com) 最近,有一位朋友因为工作需要,需要从网游的客户端编程转向服务器端编程,找我推荐一本书.我推荐了 ...

  5. GJM &colon; Unity3D - NetWork - Hight Level API &lpar; HLAPI&rpar; &lbrack;转载&rsqb;

    介绍在本系列教程中,我们将使用的网络高级API(HLAPI)来构建一个小型的多人网络案例.即使我们的例子很简单,但也会涵盖以下关键概念,这应该可以帮助大家使用HLAPI构建大型游戏项目. 在第一部分, ...

  6. Xperf Basics&colon; Recording a Trace&lpar;转&rpar;

    http://randomascii.wordpress.com/2011/08/18/xperf-basics-recording-a-trace/   This post is obsolete ...

  7. 基于SURF特征的图像与视频拼接技术的研究和实现(一)

    基于SURF特征的图像与视频拼接技术的研究和实现(一)      一直有计划研究实时图像拼接,但是直到最近拜读西电2013年张亚娟的<基于SURF特征的图像与视频拼接技术的研究和实现>,条 ...

  8. linux学习之八---Linux进程基础知识

    一.linux进程 linux是一个多用户多任务的操作系统. 多用户是指多个用户能够在同一时间使用计算机. 多任务是指linux能够同一时候运行几个任务. 进程简单来说就是执行中的程序,Linux系统 ...

  9. NavMeshAgent 动态加载障碍物

    如果你想让游戏人物绕开一些物体, 这些物体动态生成出来的.只需要给物体添加NavMeshObstacle组件即可 1. 绿色方块添加NavMeshObstacle组件 2. 红色方块没有添加NavMe ...

  10. Android 底部Dialog显示

    public void showComplainDialog() { ComplainDialog complain_dialog = new ComplainDialog(OrderDetialAc ...