Ước chung đặc biệt

View as PDF



Time limit:
Python 3 2.0s
Scratch 5.0s

Author:
Problem type
Points: 200 Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

Ước số chung đặc biệt của hai số nguyên \(a\)\(b\) là số nguyên dương \(d\) sao cho \(a\) chia hết cho \(d\), \(b\) chia hết cho \(d\), và tổng các chữ số của \(d\) là lớn nhất.

Hãy tìm ước số chung đặc biệt của hai số \(a\)\(b\).

Input

  • Trong một dòng duy nhất ghi hai số nguyên \(a, b (1 \le a, b \le 10^9)\).

Output

  • Trong một dòng duy nhất ghi ra tổng các chữ số của ước số chung đặc biệt của hai số \(a\)\(b\).

Example

Test 1

Input
220 440
Output
10
Note

Ước chung của \(220\)\(440\)\(1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110, 220\). Trong số các ước này số 55 cótổng các chữ số lớn nhất. Do đó ước chung đặc biệt của 220 và 440 là 55. Kết quả in ra là tổng các chữ số của số 55, tức là bằng 10.


Comments


  • 1
    tplong    10:49 p.m. 5 may, 2024

    lam sao de fix test 35 k tle v a

    1 reply

    • 0
      tk22NguyenHongPhuc    8:24 a.m. 2 mar, 2024

      a,b=map(int,input().split())
      def sum(x):
      r=0
      while (x>0):
      r=r+x%10
      x=x//10
      return r
      kq=0
      for i in range(1,int(a**0.5)+1):
      if (a%i==0):
      if (b%i==0):
      kq=max(kq,sum(i))
      if (b%(a//i)==0):
      kq=max(kq,sum(a//i))
      print(kq)


      • 1
        nguyentheanh2012    9:38 p.m. 10 apr, 2023 edit 2

        help


        • 0
          xuanphuc165    3:35 p.m. 23 mar, 2022

          tăng thời gian cho scratch đi anh, ít thời gian quá ạ!

          1 reply