小易学习了辗转相除法之后,就开始实践这个算法在求解最大公约数上。
牛牛给小易出了一道不同寻常的求解最大公约数: 求解a和b的最大公约数,但是a和b的范围特别大。
小易遇到了困难,向聪明的你寻求帮助,希望你能帮帮他。
第一行数字a,第二行数字b。
一行一个数字表示答案
6 4
2
7951346523609888 6998915114363550
1013754
C++
#include <iostream> #include <string> using namespace std; long long gcd(long long a, long long b) {//辗转相除 if (b == 0) return a; return gcd(b, a%b); } int main() { string s; getline(cin,s); long long a = 0, b; cin >> b; for (int i = 0; s[i] != '\0'; i++) { a = (a * 10 + s[i] - '0') % b; }//先用最大值除以最小值得到一个较小的数防止数据溢出 cout << gcd(a, b); return 0; }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String a = scanner.nextLine(); long b = scanner.nextLong(); //将这里返回的ans与b求最大公约数即可 long ans = demo2(a, b); if (ans == 0) { System.out.println(b); return; } System.out.println(gcd(ans, b)); } //将第一个很大的数long类型装不下,需要按位处理, public static long demo2(String a, long b) { //余数 long remainder = 0; //从最高位开始取一位与被除数 for (int i = 0; i < a.length(); i++) { remainder = remainder * 10 + a.charAt(i) - '0'; remainder %= b; } return remainder; } //求最大公约数 public static long gcd(long minNum, long maxNum) { //确保第一个数小于第二个数 if (minNum > maxNum) { long remp = minNum; minNum = maxNum; maxNum = minNum; } long remainder = 1; //用于保存结果 long result = 0; while (remainder != 0) { result = minNum; remainder = maxNum % minNum; maxNum = minNum; minNum = remainder; } return result; } }
def hcf(a, b): a, b = min(a, b), max(a, b) if b % a == 0: return a else: return hcf(a, b % a) a = int(input()) b = int(input()) print(hcf(a, b))
import java.math.BigDecimal; import java.util.*; public class test9{ public static void main(String []args){ Scanner sc = new Scanner(System.in); BigDecimal a = new BigDecimal(sc.nextLine()); BigDecimal b = new BigDecimal(sc.nextLine()); BigDecimal temp = a; do{ temp = a.divideAndRemainder(b)[1]; a = b; b = temp; }while(temp.longValue() != 0); System.out.println(a.longValue()); sc.close(); } }
def hcf(a, b): #a, b = min(a, b), max(a, b) if b % a == 0: return a else: return hcf( b%a, a) a = int(input()) b = int(input()) print(hcf(a, b))当a>b时在第一次调用时就会交换a,b的值,因为此时 b % a == b ,所以hcf(b%a,a)等价于hcf(b,a)
#include<iostream> using namespace std; int main() { int a,b; cin>>a>>b; int res=1; while(res) { res=a%b; a=b; b=res; } cout<<a; }就想知道我哪错了哦!为啥只能通过30%?
def fun(x, y): a = max(x, y) b = min(x, y) if a % b == 0: return b else: return fun(b, a % b) # 为啥去除这个return就不完全对呢?没想明白 a = int(input()) b = int(input()) print(fun(a,b))