首页 > 代码库 > URAL 1430. Crime and Punishment(数论)
URAL 1430. Crime and Punishment(数论)
题目链接
题意 :给你a,b,n,让你找出两个数x,y,使得n-(a*x+b*y)最小。
思路 : 分大小做,然后枚举a的倍数
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #define LL __int64 5 6 using namespace std ; 7 8 int main() 9 {10 LL a,b,n ;11 while(~scanf("%I64d %I64d %I64d",&a,&b,&n))12 {13 if(a == 1)14 {15 printf("%I64d 0\n",n) ;16 continue ;17 }18 if(b == 1)19 {20 printf("0 %I64d\n",n) ;21 continue ;22 }23 bool flag = false ;24 if(a < b)25 {26 swap(a,b) ;27 flag = true ;28 }29 LL t = min(n/a,b) ,x;30 LL minn = 999999999LL ;31 for(int i = 0; i <= t ; i++)32 {33 if((n - a * i) % b < minn)34 {35 minn = (n - a * i) % b ;36 x = i;37 }38 }39 if(!flag) printf("%I64d %I64d\n",x,(n-a*x)/b) ;40 else printf("%I64d %I64d\n",(n-a*x)/b,x) ;41 }42 return 0 ;43 }
URAL 1430. Crime and Punishment(数论)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。