首页 > 代码库 > 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 }
View Code

 

URAL 1430. Crime and Punishment(数论)