0

我们如何编写代码来找到以下解决方案： (N+1)*X =LCM( 1,2,3,4,5,6,......,N,N+1) 使用 mod 当它变得大于 (10^9 +7) 。使用 MOD=(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;
    }
}
4

1 回答 1

0

我假设这是你的问题（如果我错了，请纠正我）：

当 N*X = LCM(1 -> N) (mod 1E9 +7) 时求 X

首先，得到 LCM(1 -> N)，然后除以 N。

您可以查看每个≤ N 的质数并取≤ N 的最高指数，然后将它们全部相乘，而不是计算每个数字的 LCM，直到 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 整除。你能澄清这个问题需要什么吗？您是否必须找到等于 LCM(1->23) 的 X*N (mod 1E9 +7)？

于 2013-12-08T17:59:09.383 回答