时间戳

首页 > 解决方案 > 什么是大数的gcd

c++ - 什么是大数的gcd

问题描述

当我试图找到大数的 gcd 时，其中一个数字是 10 ^ 250，另一个数字介于 100000 之间。尝试在 c++ 中执行此操作时遇到一个错误，我无法弄清楚，但 python3 中的相同代码有效美好的。

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll gcd(ll n,ll mod)
{
    if(!n)
    return mod;
    return (mod%n,n);
}
ll getmod(ll n,char b[])
{
    ll mod = 0;
    for(int i =0;i<strlen(b);i++)
    {
        mod = mod * 10 + b[i];
        mod %= n;
    }
    return mod;
}
int main() {
    // your code goes here
    ll n;
    string m;
    cin>>n;
    getline(cin, m);
    int mod = getmod(n,m);
    int result = gcd(n,mod);
    cout<<result;
    return 0;
}

输出

prog.cpp: In function 'int main()':
prog.cpp:26:22: error: cannot convert 'std::__cxx11::string {aka std::__cxx11::basic_string<char>}' to 'char*' for argument '2' to 'll getmod(ll, char*)'
  int mod = getmod(n,m);
                      ^

标签： c++

解决方案

您可以使用以下程序计算两个数字的 GCD，其中一个非常大，另一个适合intorlong long数据类型。

#include <iostream>
#include <algorithm>

int calculateRemainder(std::string dividend,int divisor){
    int remainder = 0;

    for(int i = 0 ; i < dividend.size() ; ++i){
        remainder = (remainder * 10 + (dividend[i] - '0')) % divisor;
    }

    return remainder;
}

int calculateGCD(std::string a, int b){
    int remainder = calculateRemainder(a,b); // only one call to calculateRemainder is needed,
                                            // after that the gcd calculation is trivial
                                            // because gcd of two numbers is never greater than the minimum of two
    return std::__gcd(b, remainder);
}

int main(){
    std::string a;  // can be very big, in the order of 10^250 or more
    int b; // <= 10^9
    std::cin >> a >> b;
    int result = calculateGCD(a,b);
    std::cout << result << "\n";
    return 0;
}

推荐阅读