8.24阿里笔试

第一题 10 分钟 AC，第二题 50 分钟 0AC。爆炸。 *** 约分就好，再看 A/a 和 B/b 哪个小，小的那个就是共同的倍数。

一个小时磨第一题，以下代码能AC import java.util.*; public class Main {     public static void main(String args[]) {         Scanner input = new Scanner(System.in);         while(input.hasNextInt()){             long A = input.nextLong();             long B = input.nextLong();             long a = input.nextLong();             long b = input.nextLong();             long start = Math.min(A, (B*a)/b);             for (long i = start; i >= 1 ; i--) {                 if((b*i)%a == 0 && (b*i)/a <= B){                     long y = (b*i)/a;                     System.out.println(i + " " + y);                     break;                 }             }         }     } }

贴一下我的代码，供大家参考😀

第一题，根据公式可以推导出x=(a/b)*y, 那么x*y就完全取决于y，可以推导y的范围是[1,B]以及[b/a, (b/a)*A]，求出y满足这两个范围，且使得x为整数的(x,y)就可以了 package AliBaBa; import java.util.Scanner; public class probleam1 {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         while(sc.hasNext()){             long A = sc.nextLong();             long B = sc.nextLong();             long a = sc.nextLong();             long b = sc.nextLong();             //临时变量  先取到最大的那一个             long tem =  Math.min(B, (b*A)/a);             //往小了缩，直到x为整数             while(tem >= Math.ceil((double)b/a) && tem >= 1 && (a*tem)%b != 0){                 tem--;             }             //不存在，到底了也没有能够满足的             if((a*tem)%b != 0){                 System.out.println(0 + " " + 0);             }else{                 long y = tem;                 long x = (a*y)/b;                 System.out.println(x + " " + y);             }         }     } }

昨天做完腾讯：我完了我完了... 今天做完阿里：昨天做的好像也还行？

import java.util.Scanner; public class ali {     public static void main(String[] args) {         Scanner in = new Scanner(System.in);         long X = in.nextInt();         long Y = in.nextInt();         int a = in.nextInt();         int b = in.nextInt();         while(X*b!=Y*a&X>=1&Y>=1){             if(X*b>Y*a){                 X=Y*a/b;             }             if(X*b<Y*a){                 Y=X*b/a;             }         }         if(X==0||Y==0){             System.out.println("0 0");         }         else {             System.out.println(X+" "+Y);         } }只做出来第一道

先对将a/b约分，防止a或b太大，超过范围 然后就以此a和b同时增倍直到最大

第一题：第一个是直接算的解析解，常数时间复杂度，第二个是从大到小遍历b/gcd(a,b)的倍数，O(n)复杂度

感谢阿里让我认清自己的实力+1

第一题一个循环都会超时。。。。要再减一点，x必须是a的倍数

太菜了 0.1 0的路过

求题目描述

牛客我把视频挂断，没退出房间，对面面试官能听到我说话吗？

简直佛了自己了  不知道***这个玩意

第二题可以用弗洛伊德算法的变体

  求问各位大佬，这种写法，只过40%，是因为没用long还是因为用了for循环啊？

第二题或许可以用MST解

1: 0.9, 2: 0, c++

可以发下题目吗