fork(1) download
copy 
  1. # Variation on multiply (2).
  2. # @see bOJ7Zy
  3.  
  4. # Conversion.
  5.  
  6. def iton(x):
  7.     r = []
  8.     while True:
  9.         x, y = divmod(x, 10)
  10.         r.append(y)
  11.         if x == 0:
  12.             return r
  13.  
  14. def ntos(a):
  15.     return ''.join(map(str, reversed(a)))
  16.  
  17. # Math.
  18.  
  19. def _iszero(a):
  20.     return len(a) == 1 and a[0] == 0
  21.  
  22. def _zeroextend(a, n):
  23.     return a[:] + [0] * (n - len(a))
  24.  
  25. def _zeroreduce(a):
  26.     n = len(a)
  27.     while n != 1 and a[n-1] == 0:
  28.         n -= 1
  29.     return a[:n]
  30.  
  31. def nshl(a, n):
  32.     return _zeroreduce([0] * n + a[:])
  33.  
  34. def nshr(a, n):
  35.     return _zeroextend(a[n:], 1)
  36.  
  37. def nadd(a, b):
  38.     n = 1 + max(len(a), len(b))
  39.     r = _zeroextend(a, n)
  40.     b = _zeroextend(b, n)
  41.     c = 0
  42.     for i in range(n):
  43.         c, r[i] = divmod(r[i] + b[i] + c, 10)
  44.     return _zeroreduce(r)
  45.  
  46. def _mul1(a, x):
  47.     assert 0 <= x < 10
  48.     n = 1 + len(a)
  49.     r = _zeroextend(a, n)
  50.     c = 0
  51.     for i in range(n):
  52.         c, r[i] = divmod(r[i] * x + c, 10)
  53.     return _zeroreduce(r)
  54.  
  55. def nmul(a, b):
  56.     if _iszero(b):
  57.         return [0]
  58.     return nadd(_mul1(a, b[0]), nmul(nshl(a, 1), nshr(b, 1)))
  59.  
  60. # Test.
  61.  
  62. n = 50
  63. for x in range(0, n+1):
  64.     for y in range(0, n+1):
  65.         # nadd
  66.         u = int(ntos(nadd(iton(x), iton(y))))
  67.         v = x + y
  68.         assert u == v, f'{x} + {y}; {u}, {v}'
  69.         # nmul
  70.         u = int(ntos(nmul(iton(x), iton(y))))
  71.         v = x * y
  72.         assert u == v, f'{x} * {y}; {u}, {v}'
  73.  
  74. def show(y):
  75.     return y, ntos(y)
  76.  
  77. x = 123
  78. print(show(iton(0)))
  79. print(show(iton(1)))
  80. print(show(iton(x)))
  81. print('-')
  82. print(show(nadd(iton(0), iton(0))))
  83. print(show(nadd(iton(1), iton(1))))
  84. print(show(nadd(iton(x), iton(x))))
  85. print('-')
  86. print(show(nmul(iton(0), iton(0))))
  87. print(show(nmul(iton(0), iton(1))))
  88. print(show(nmul(iton(1), iton(0))))
  89. print(show(nmul(iton(1), iton(1))))
  90. print(show(nmul(iton(x), iton(1))))
  91. print(show(nmul(iton(1), iton(x))))
  92. print(show(nmul(iton(x), iton(x))))
  93. print(show(nmul(iton(x), iton(x*x))))
  94. print(show(nmul(iton(x*x), iton(x))))
Success #stdin #stdout 0.09s 9764KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
([0], '0')
([1], '1')
([3, 2, 1], '123')
-
([0], '0')
([2], '2')
([6, 4, 2], '246')
-
([0], '0')
([0], '0')
([0], '0')
([1], '1')
([3, 2, 1], '123')
([3, 2, 1], '123')
([9, 2, 1, 5, 1], '15129')
([7, 6, 8, 0, 6, 8, 1], '1860867')
([7, 6, 8, 0, 6, 8, 1], '1860867')
https://ideone.com/6SDvDi
language:
Python 3 (python  3.9.5)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!