math - 1000000007 を法とする n 数の最小公倍数

Question

n 個の数値 MODULO 10^9+7 の LCM を見つける必要があります。すべての要素。間違っていますか?

Answer 1

今後の参考のために、素因数分解を使用しない C++ 実装を次に示します。

考えられる解決策の 1 つは、答えの要素の配列を保持することです。各係数は、1..N の各数値を GCD(数値, [以前のすべての数値]) で割ったものになります。これを機能させるには、単一の数値と因数の配列の間の結果を計算する特別な GCD をコーディングする必要があります。この C++ コードは、これがどのように機能するかを示しています。

#include <iostream>
#include <vector>
#define lli long long int
using namespace std;

vector<lli> T;

lli gcd(lli a, lli b) {
    if(b == 0) 
        return a;
    return gcd(b, a%b);
}

lli gcd_vector(vector<lli>& a, lli b) {
    lli ma = 1;
    for(int i=0; i<T.size(); i++)
        ma = ma*T[i]%b;
    return gcd(b, ma);
}

int main() {
    lli answer = 1;
    for(int i=1; i<=1000; i++) {
        lli factor = i/gcd_vector(T, i); 
        T.push_back(factor);
        answer = (answer*factor)%1000000007;
    }

    cout << answer << endl;
}