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 を見て、≤ 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 に答える