Программа для вычисления LCM из K последовательных чисел mod 1000000007 с низкой сложностью

Question

Мне нужно написать программу такую, что для нескольких запросов типа L, R мне нужно вывести LCM чисел от L до R. где R может max перейти к M

Мне удалось написать программу сложности N (Q) .M, Мне нужно сделать это в N (Q) .Log (M) или N (Q) .sqrt (M) ,

Здесь N (Q) обозначает отсутствие запросов. sqrt обозначает квадратный корень.

EDIT: Я написал его с помощью Segmentree, однако получить неправильный ответ, здесь powf находит^Ь% P во время LogN: Моего код запроса:

long long findfunc(long long ql,long long qr,long long ind) 
    { 
if(a >qr || b<ql) 
    return 1; 
if(a>=ql && b<=qr) 
    { //cout<<"LCM "<<ql<<" to "<<qr<<" "<<val[ind]<<endl; 
    return val[ind]%mod; 
    } 
else 
    { 
ll vl= findfunc(ql,qr,2*ind+1); 
ll vr= findfunc(ql,qr,2*ind+2); 
return (((vl*vr)%mod) * powf(gcd(vl,vr),mod-2) )%mod; 
} 
} 

Answer 1

Вы ищете структуру данных, которая называется Segment Trees , Я не буду предоставлять код, потому что это не то, что мы делаем здесь на SO.

Эта ссылка:

https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/

будет вам помочь.

Answer 2

Вы можете использовать segment tree. Идея состоит в том, чтобы хранить наименьший общий кратный l, l+1, ..., r в каждом узле, представляющем интервал [l, r].

• как построить - вы начинаете снизу вверх, и когда вы должны слиться с узлами [a, b], [b+1, c] вы делаете следующее. Пусть lcm([a, b]) = l1 и lcm([b+1, c]) = l2 затем lcm([a, c]) = lcm(lcm([a, b]), lcm([b+1, c])) = lcm(l1, l2) = l1*l2/gcd(l1,l2). Поскольку gcd(l1,l2) примерно постоянна, операция слияния постоянна.

• как запросить - если у вас есть интервал [a, b] вы нашли узел в дереве таким образом, что они представляют собой диапазоны [a, c] и [c+1, b] для некоторых c. Тогда вычисление lcm([a, b]) будет таким же, как на этапе слияния.

Answer 3

Я не эксперт на C++, вы можете взглянуть на мою реализацию C#, я считаю, что это не сложно преобразовать в C++.

private const int Mid = 128 * 1024; 
private static long mod = 1000000007; 
private static long[] t = new long[Mid + Mid]; 
public static void Initialize(long[] a) 
{ 
    for (int i = 0; i < a.Length; i++) t[Mid + i] = a[i]; 
    for (int i = a.Length; i < Mid; i++) t[Mid + i] = 1; 
    for (int i = Mid - 1; i > 0; i--) t[i] = LCM(t[i + i], t[i + i + 1]); 
} 

public static long GetLcm(int l, int r) 
{ 
    l += Mid; 
    r += Mid; 
    long ans = 1; 
    while (l <= r) 
    { 
     ans = LCM(ans, t[l]); 
     ans = LCM(ans, t[r]); 

     l = (l + 1)/2; 
     r = (r - 1)/2; 
    } 

    return ans; 
} 

public static void Update(int i, long v) 
{ 
    i += Mid; 
    t[i] = v; 
    while (i > 0) 
    { 
     i = i/2; 
     t[i] = LCM(t[i + i], t[i + i + 1]); 
    } 
} 

private static long GCD(long a, long b) 
{ 
    if (a % b == 0) return b; 
    return GCD(b, a % b); 
} 

private static long LCM(long a, long b) 
{ 
    if (a == 0 || b == 0) return 0; 
    return ((a * b)/GCD(a, b)) % mod; 
} 

вы можете использовать его с помощью следующего кода:

long[] m = new long[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 
    Initialize(m); 
    var ans1 = GetLcm(0, 9); 
    Update(8, 6); 
    var ans2 = GetLcm(0, 9); 

Это не оптимальное решение, но должна работать корректно. В качестве структуры данных используется сегментное дерево. Если вам действительно не нужна операция обновления, SparseTable также будет использоваться здесь.