首页 > 其他 > 详细

买不到的数目

时间:2019-03-16 00:42:53      阅读:90      评论:0      收藏:0      [点我收藏+]

标签:clas   ==   最小   system.in   col   args   ava   detail   print   

方法一:自然数a,b互质,则不能表示成ax+by(x,y为非负整数)的最大整数是ab-a-b. 

证明:
a或者b是1的情况下容易证明.
以下情况都是a>1且b>1的情况.
首先证明ab-a-b不能表示成ax+by
假设ab-a-b=ax+by,那么ab=am+bn (m,n都大于等于1)
左边是a的倍数,右边am是a的倍数,那么要求bn也要是a的倍数
b不是a的倍数,只能要求n是a的倍数,这样的话,bn=bn’a>=ba
那么am=ab-bn<=0就与am>1矛盾.

(方法一没有想到)
 方法二就是暴力,从最小公倍数暴力!

 
import java.sql.Date;
import java.util.*;

public class Main1 {
    public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int m = sc.nextInt();
      int w = m*n;
      int count=0;
      int flag=1;
      long start = System.currentTimeMillis();
      while(w-->0){
          count=0;
          for(int i=0;i<m;i++){
              if(flag==0)
              {
                  flag=1;break;
              }
              for(int j=0;j<n;j++){
                  if(i*n+j*m==w)
                  {
                     flag=0;
                     break;
                  }
                 count++; 
              }
          }
          if(count==m*n){
              System.out.println(w);
          break;
          }
      }
      long end = System.currentTimeMillis();
      System.out.println(end-start);
    }

    
 
    
     
}

参考博客:https://blog.csdn.net/bear_huangzhen/article/details/78496671 

买不到的数目

标签:clas   ==   最小   system.in   col   args   ava   detail   print   

原文:https://www.cnblogs.com/ls-pankong/p/10540183.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号