我们从Python开源项目中，提取了以下38个代码示例，用于说明如何使用math.gcd()。
def canMeasureWater(self, x, y, z): """ :type x: int :type y: int :type z: int :rtype: bool """ if x + y < z: return False if z <= 0 or x == z or y == z or x + y == z: return True return z % gcd(x, y) == 0 # Can also be done using bfs but that's slower # https://discuss.leetcode.com/topic/50425/breadth-first-search-with-explanation/2
def _verify_params(self): phi = (self.p - 1) * (self.q - 1) if self.p == self.q: raise ValueError("p and q cannot be identical") # verify that p and q are far enough apart - https://crypto.stackexchange.com/a/35096 if self.n >= 1024 and abs(self.p - self.q).bit_length() <= (self.n.bit_length() // 2 - 100): raise ValueError("p and q are too close together") if not is_prime(self.p): raise ValueError("p must be a prime (probabilistic)") if not is_prime(self.q): raise ValueError("q must be a prime (probabilistic)") if not (1 < self.e < phi): raise ValueError("e must be between 1 and (p-1)(q-1)") if gcd(self.e, phi) != 1: raise ValueError("e must be co-prime to (p-1)(q-1)")
def __init__(self, pq=None, seed=None): if pq is not None: if len(pq) != 2: raise ValueError("Parameter pq must be a triple of the values p and q") self.p, self.q = pq self.n = self.p * self.q self._verify_params() else: self._gen_params(511) self.x = None if not seed: seed = SystemRandom().randrange(1, self.n) while gcd(seed, self.n) != 1: seed = SystemRandom().randrange(1, self.n) super().__init__(seed)
def lcm(a, b): return (a * b) // math.gcd(a, b)
def compute_bin_size(dfs): bin_sizes = [] for df in dfs.values(): bins = df.head(100000).index.get_level_values("Bin").astype(int) bin_size = reduce(gcd, bins) bin_sizes.append(bin_size) assert len(set(bin_sizes)) == 1, "Matrixes have different bin sizes: " + str(bin_sizes) bin_size = bin_sizes.pop() logging.info("Bin size: " + str(bin_size)) return bin_size
def gcd_of_list(l): return reduce(gcd, l, 0)
def test_alg_euclides(self, a, b): x, y, d = alg_euclides(a, b) assert x * a + y * b == d assert d == gcd(a, b) if (a // b) * b != a and (b // a) * a != b: # a no divide a b y viceversa assert x < b // d assert y < a // d
def test_alg_euclides_polinomios(self, l1, l2, primo): assume(l1) assume(l2) g = PolinomioZp(l1, primo) h = PolinomioZp(l2, primo) cero = PolinomioZp([0], primo) assume(g != cero) s, t, d = alg_euclides_polinomios(g, h, p=primo) assert s * g + t * h == d assert g % d == 0 and h % d == 0 # vemos si el gcd divide a ambos if h != cero: assert s.grado() <= h.grado() and t.grado() <= g.grado()
def egypt_greedy(x, y): if x == 1: return [y] else: a = (-y) % (x) b = y*(y//x + 1) c = gcd(a, b) if c > 1: num, denom = a//c, b//c else: num, denom = a, b return [y//x + 1] + egypt_greedy(num, denom)
def rsa_recover_prime_factors(n, e, d): """ Compute factors p and q from the private exponent d. We assume that n has no more than two factors. This function is adapted from code in PyCrypto. """ # See 8.2.2(i) in Handbook of Applied Cryptography. ktot = d * e - 1 # The quantity d*e-1 is a multiple of phi(n), even, # and can be represented as t*2^s. t = ktot while t % 2 == 0: t = t // 2 # Cycle through all multiplicative inverses in Zn. # The algorithm is non-deterministic, but there is a 50% chance # any candidate a leads to successful factoring. # See "Digitalized Signatures and Public Key Functions as Intractable # as Factorization", M. Rabin, 1979 spotted = False a = 2 while not spotted and a < _MAX_RECOVERY_ATTEMPTS: k = t # Cycle through all values a^{t*2^i}=a^k while k < ktot: cand = pow(a, k, n) # Check if a^k is a non-trivial root of unity (mod n) if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1: # We have found a number such that (cand-1)(cand+1)=0 (mod n). # Either of the terms divides n. p = gcd(cand + 1, n) spotted = True break k *= 2 # This value was not any good... let's try another! a += 2 if not spotted: raise ValueError("Unable to compute factors p and q from exponent d.") # Found ! q, r = divmod(n, p) assert r == 0 p, q = sorted((p, q), reverse=True) return (p, q)
def mul_by_constant_modN(eng, c, N, quint_in): """ Multiplies a quantum integer by a classical number a modulo N, i.e., |x> -> |a*x mod N> (only works if a and N are relative primes, otherwise the modular inverse does not exist). """ assert(c < N and c >= 0) assert(gcd(c, N) == 1) n = len(quint_in) quint_out = eng.allocate_qureg(n + 1) for i in range(n): with Control(eng, quint_in[i]): AddConstantModN((c << i) % N, N) | quint_out for i in range(n): Swap | (quint_out[i], quint_in[i]) cinv = inv_mod_N(c, N) for i in range(n): with Control(eng, quint_in[i]): SubConstantModN((cinv << i) % N, N) | quint_out del quint_out # calculates the inverse of a modulo N
def _gen_param_e(self): # use builtin RNG rand = SystemRandom() phi = (self.p - 1) * (self.q - 1) self.e = rand.randint(2, phi - 1) while gcd(self.e, phi) != 1: self.e = rand.randint(2, phi - 1)
def _gen_param_e(self): # use builtin RNG rand = SystemRandom() n_bits = self.n.bit_length() phi = (self.p - 1) * (self.q - 1) mx = min(phi - 1, n_bits // 80) # top limits are phi (exclusive) and N/80 (inclusive) self.e = rand.randint(2, mx) while gcd(self.e, phi) != 1: self.e = rand.randint(2, mx)
def seed(self, a=None, version=2): """Initialize the internal state of the generator.""" if not (1 <= a <= self.n - 1): raise ValueError("Seed value must be between 1 and n-1=" + str(self.n - 1)) if gcd(a, self.n) != 1: raise ValueError("Seed value must be co-prime to n=" + str(self.n)) super().seed(a, version) self.x = pow(a, 2, self.n)
def print_results(best_result): _, nominator, denominator = best_result # print results from math import gcd gcd_of_both = gcd(nominator, denominator) print("{}/{}".format( nominator // gcd_of_both, denominator // gcd_of_both )) exit()
def extract_n_elements(l, n): while not gcd(n, len(l)) == n: l.pop(0) len_div = len(l) step = len_div // n ids = [i - 1 for i in np.arange(step, len_div + step, step)] # -1 for indexing elements = np.asarray(l)[ids].tolist() return elements
def populate_folds(yes_questions, no_questions, mb_size, verbose=False): yes_to_pop, no_to_pop = yes_questions[:], no_questions[:] num_questions = len(yes_questions) + len(no_questions) min_fold_len = (num_questions - mb_size * GlobalConfigs.NUM_TEST_FOLDS) // GlobalConfigs.NUM_TEST_FOLDS # TODO loosing questions task_folds = [[] for _ in range(GlobalConfigs.NUM_TEST_FOLDS)] assert mb_size % 2 == 0 # must be even # populate for i in range(GlobalConfigs.NUM_TEST_FOLDS): while gcd(mb_size, len(task_folds[i])) != mb_size or len(task_folds[i]) < min_fold_len: task_folds[i].append(yes_to_pop.pop()) task_folds[i].append(no_to_pop.pop()) if verbose: print('fold {} length: {}'.format(i, len(task_folds[i]))) return task_folds
def gen_task_mbs(self, style, test_fold_id): num_task_iterations = int(''.join([c for c in self.regime if c.isdigit()])) # make blocks if style == 'train': task_lines = list(chain(*[fold for n, fold in enumerate(self.task_folds) if n != test_fold_id])) windows_x, windows_y = self.make_windows(task_lines) block_x = np.tile(windows_x, [num_task_iterations, 1]) block_y = np.tile(windows_y, [num_task_iterations, 1]) elif style == 'test': task_lines = list(chain(*[fold for n, fold in enumerate(self.task_folds) if n == test_fold_id])) windows_x, windows_y = self.make_windows(task_lines) block_x = windows_x block_y = windows_y elif style == 'train1': task_lines = list(chain(*[fold for n, fold in enumerate(self.task_folds) if n != test_fold_id])) windows_x, windows_y = self.make_windows(task_lines) block_x = windows_x block_y = windows_y else: raise AttributeError('rnnlab: Invalid arg to "style"') # split to mbs if not gcd(self.mb_size, len(block_x)) == self.mb_size: raise Exception( 'rnnlab: Number of task_lines must be divisible by mb_size') num_splits = len(block_x) // self.mb_size # generate for x, y in zip(np.vsplit(block_x, num_splits), np.vsplit(block_y, num_splits)): yield x, y
def _safe_math_gcd(a, b): safe_a = Number(a) safe_b = Number(b) if safe_a == 0 and safe_b == 0: return 0 else: return math.gcd(safe_a.__float__(), safe_b.__float__())
def __construct_byset(self, start, byxxx, base): """ If a `BYXXX` sequence is passed to the constructor at the same level as `FREQ` (e.g. `FREQ=HOURLY,BYHOUR={2,4,7},INTERVAL=3`), there are some specifications which cannot be reached given some starting conditions. This occurs whenever the interval is not coprime with the base of a given unit and the difference between the starting position and the ending position is not coprime with the greatest common denominator between the interval and the base. For example, with a FREQ of hourly starting at 17:00 and an interval of 4, the only valid values for BYHOUR would be {21, 1, 5, 9, 13, 17}, because 4 and 24 are not coprime. :param start: Specifies the starting position. :param byxxx: An iterable containing the list of allowed values. :param base: The largest allowable value for the specified frequency (e.g. 24 hours, 60 minutes). This does not preserve the type of the iterable, returning a set, since the values should be unique and the order is irrelevant, this will speed up later lookups. In the event of an empty set, raises a :exception:`ValueError`, as this results in an empty rrule. """ cset = set() # Support a single byxxx value. if isinstance(byxxx, integer_types): byxxx = (byxxx, ) for num in byxxx: i_gcd = gcd(self._interval, base) # Use divmod rather than % because we need to wrap negative nums. if i_gcd == 1 or divmod(num - start, i_gcd)[1] == 0: cset.add(num) if len(cset) == 0: raise ValueError("Invalid rrule byxxx generates an empty set.") return cset
def extended_euclid(a: int, b: int) -> Tuple[int, int, int]: """Extended Euclidean algorithm that computes the Bézout coefficients as well as :math:`gcd(a, b)` Returns ``x, y, d`` where *x* and *y* are a solution to :math:`ax + by = d` and :math:`d = gcd(a, b)`. *x* and *y* are a minimal pair of Bézout's coefficients. See `Extended Euclidean algorithm <https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm>`_ or `Bézout's identity <https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity>`_ for more information. Example: Compute the Bézout coefficients and GCD of 42 and 12: >>> a, b = 42, 12 >>> x, y, d = extended_euclid(a, b) >>> x, y, d (1, -3, 6) Verify the results: >>> import math >>> d == math.gcd(a, b) True >>> a * x + b * y == d True Args: a: The first integer. b: The second integer. Returns: A tuple with the Bézout coefficients and the greatest common divider of the arguments. """ if b == 0: return (1, 0, a) x0, y0, d = extended_euclid(b, a % b) x, y = y0, x0 - (a // b) * y0 return (x, y, d)
def solve_linear_diop(total: int, *coeffs: int) -> Iterator[Tuple[int, ...]]: r"""Yield non-negative integer solutions of a linear Diophantine equation of the format :math:`c_1 x_1 + \dots + c_n x_n = total`. If there are at most two coefficients, :func:`base_solution_linear()` is used to find the solutions. Otherwise, the solutions are found recursively, by reducing the number of variables in each recursion: 1. Compute :math:`d := gcd(c_2, \dots , c_n)` 2. Solve :math:`c_1 x + d y = total` 3. Recursively solve :math:`c_2 x_2 + \dots + c_n x_n = y` for each solution for `y` 4. Combine these solutions to form a solution for the whole equation Args: total: The constant of the equation. *coeffs: The coefficients :math:`c_i` of the equation. Yields: The non-negative integer solutions of the equation as a tuple :math:`(x_1, \dots, x_n)`. """ if len(coeffs) == 0: if total == 0: yield tuple() return if len(coeffs) == 1: if total % coeffs[0] == 0: yield (total // coeffs[0], ) return if len(coeffs) == 2: yield from base_solution_linear(coeffs[0], coeffs[1], total) return # calculate gcd(coeffs[1:]) remainder_gcd = math.gcd(coeffs[1], coeffs[2]) for coeff in coeffs[3:]: remainder_gcd = math.gcd(remainder_gcd, coeff) # solve coeffs[0] * x + remainder_gcd * y = total for coeff0_solution, remainder_gcd_solution in base_solution_linear(coeffs[0], remainder_gcd, total): new_coeffs = [c // remainder_gcd for c in coeffs[1:]] # use the solutions for y to solve the remaining variables recursively for remainder_solution in solve_linear_diop(remainder_gcd_solution, *new_coeffs): yield (coeff0_solution, ) + remainder_solution
