LCM из N+1 последовательных номеров

Как мы можем написать код, чтобы найти решение следующего: (N+1)*X =LCM( 1,2,3,4,5,6,......,N,N+1) использовать мод, когда он становится больше, чем (10^9 +7) . ИСПОЛЬЗОВАТЬ МОД=(10^9 +7). Я написал следующий фрагмент кода, но он не работает:

ll dp[100005];
ll gcd (ll a,ll b)
 {
        if (b == 0)
                return a;
        else
                return gcd (b, a % b);
}
void extend_euclid(int a,int b,int &x,int &y)
{
    if(a==0)
    {
                x=0;y=1;
                return;
        }
        int x1,y1;
        extend_euclid(b%a,a,x1,y1);
        x=y1-(b/a)*x1;
        y=x1;
}
void init()
{
    dp[1]=1;
    for(ll i=2;i<100002;i++)
    {
        ll x,y;
        x=dp[i-1]*i;
        x=x%mod;
        y=gcd(i,dp[i-1]);
        y=y%mod;
                int z1,z2;
        extend_euclid(y,mod,z1,z2);
                y=(z1+mod)%mod;
                dp[i]=(y*x)%mod;
    }
}

modulo lcm
person Prakash Mishra    schedule 10.03.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Я предполагаю, что это ваша проблема (поправьте меня, если я ошибаюсь):

Найдите X для случая, когда N*X = LCM(1 -> N) (mod 1E9 +7)

Сначала получите НОК(1 -> N), затем разделите на N.

Вместо того, чтобы вычислять НОК каждого числа до N, вы можете посмотреть на каждое простое число ≤ N и взять самый высокий показатель степени, равный ≤ N, перемножив их все вместе. Итак, если N=20, вы должны взять: 16(2^4), 9(3^2), 5, 7, 11, 13, 19. Перемножив их вместе, вы получите 232792560, что равно LCM(1 - > 20).

При этом N ВСЕГДА будет делиться на LCM(1->N) (я оставлю вас, чтобы понять, почему), и найти X легко.

Теперь вы заметите, что при N = 23 вы должны (mod 1E9 +7) и ваш LCM (1-> 23) не делится на 23. Можете ли вы уточнить, что требует вопрос? Вам нужно найти X*N (mod 1E9 +7), который бы равнялся LCM(1->23)??

person user2514440    schedule 08.12.2013