Мод B, A и B очень большие числа

Question

Я хочу знать, являются ли A и B относительно простое с использованием евклидова алгоритма. A и B - большие числа, которые не могут быть сохранены в любом типе данных (на C), поэтому они хранятся в связанном списке. В алгоритме используется оператор %. Мой вопрос в том, есть ли способ вычислить для A mod B, фактически не используя непосредственно оператор %. Я узнал, что % дистрибутивна более того:

A%B = ((a1%B)+(a2%B))%B. 

Но проблема все еще сохраняется, потому что я по-прежнему будет делать %B операции.

Answer 1

Вам необходимо рассчитать a % b без оператора %. ОК? По определению modulo operation находит remainder после деления одного числа на другое.

В питона:

# mod = a % b 
def mod(a, b): 
    return a-b*int(a/b) 

>>> x = [mod(i,j) for j in range(1,100) for i in range(1,100)] 
>>> y = [i % j for j in range(1,100) for i in range(1,100)] 
>>> x == y 

Правда

В C++:

#include <iostream> 
#include <math.h> 
using namespace std; 

unsigned int mod(unsigned int a, unsigned int b) { 
    return (unsigned int)(a-b*floor(a/b)); 
} 

int main() { 
    for (unsigned int i=1; i<=sizeof(unsigned int); ++i) 
     for (unsigned int j=1; j<=sizeof(unsigned int); ++j) 
      if (mod(i,j) != i%j) 
       cout << "Somthing wrong!!"; 
    cout << "Proved for all unsigned int!"; 
    return 0; 
} 

Доказанные для всех неподписанных Int!

Теперь просто увеличьте результат до своих больших чисел ... !!!