2

問題：見つける

ここに画像の説明を入力

nの範囲: 1<= n <=ここに画像の説明を入力

主な課題は、大きくなる可能性のあるクエリ (Q) の処理です。1 <= Q <=ここに画像の説明を入力

これまでに使用した方法：

強引な

while(Q--)
{
    int N;
    cin>>N;
    for(int i=1;i<=N;i++)
        ans += lcm(i,N)/i ;
}

複雑さ :ここに画像の説明を入力

でのクエリの前処理と処理ここに画像の説明を入力

最初に、すべての N のオイラー totient 関数の値を保持するテーブルを作成します。これは O(N) で実行できます。

void sieve()
{
    // phi table holds euler totient function value
    // lp holds the lowest prime factor for a number
    // pr is a vector which contains prime numbers 
    phi[1]=1;
    for(int i=2;i<=MAX;i++)
    {
        if(lp[i]==0)
        {
            lp[i]=i;
            phi[i]=i-1;
            pr.push_back(i);
        }
        else
        {
            if(lp[i]==lp[i/lp[i]])
                phi[i] = phi[i/lp[i]]*lp[i];
            else phi[i] = phi[i/lp[i]]*(lp[i]-1);
        }
    for(int j=0;j<(int)pr.size()&&pr[j]<=lp[i]&&i*pr[j]<=MAX;j++)
        lp[i*pr[j]] = pr[j];
}

各クエリに対して N を因数分解d*phi[d]し、結果に追加します。

for(int i=1;i*i<=n;i++)
{
   if(n%i==0)
   {
    // i is a factor
    sum += (n/i)*phi[n/i];
    if(i*i!=n)
        {
            // n/i is a factor too
            sum += i*phi[i];
        }
   }
}

これには O(sqrt(N)) が必要です。

複雑さ : O(Q*sqrt(N))

O(1) でクエリを処理する

上で説明したふるい法に、必要な答えを O(NLogN) で計算する部分を追加します。

for(int i=1;i<=MAX;++i)
{
    //MAX is 10^7
    for(int j=i;j<=MAX;j+=i)
    {
        ans[j] += i*phi[i];
    }
}

残念ながら、これは指定された制約と制限時間 (1 秒) でタイムアウトになります。

これには、 N の素因数分解に関する巧妙なアイデアが含まれていると思います。上記で作成した lp(lowest prime) テーブルを使用して O(LogN) の数値を素因数分解できますが、因数分解を使用して答えに到達する方法がわかりません。

4

1 に答える 1

0

次のアルゴリズムを試すことができます。

lcm(i,n) / i  = i * n / i * gcd(i, n) = n / gcd(i, n)

今すぐ数値の合計を見つける必要がありますn / gcd(i, n)。

n = p1^i1 * p2^i2 * p3^j3数p1, p2, ... pkが素数であることを許可します。

の項目数なn / gdc(i, n)ので、 sum に追加しgcd(i , n) == 1ます。phi[n] = n*(p1-1)*(p2-1)*...*(pk-1)/(p1*p2*...*pk)n*phi[n]

の項目数なn / gdc(i, n)ので、 sum に追加しgcd(i , n) == p1ます。 phi[n/p1] = (n/p1)*(p1-1)*(p2-1)*...*(pk-1)/(p1*p2*...*pk)n/p1*phi[n/p1]

の項目数なn / gdc(i, n)ので、 sum に追加しgcd(i , n) == p1*p2ます。 phi[n/(p1*p2)] = (n/(p1*p2))*(p1-1)*(p2-1)*...*(pk-1)/(p1*p2*...*pk)n/(p1*p2)*phi[n/(p1*p2)]

今答えは合計です

n/(p1^j1*p2^j2*...*pk^jk)  phi[n/(p1^j1*p2^j2*...*pk^jk)]

全体

j1=0,...,i1  
j2=0,...,i2
....  
jk=0,...,ik

この合計のアイテムの総数はi1*i2*...*ik、O(n) よりも大幅に少なくなります。

この合計を計算するには、自由な引数の初期番号、現在の表現、および初期表現で再帰関数を使用できます。

initial = {p1:i1, p2:i2, ... ,pn:in} 
current = {p1:i1, p2:i2, ... ,pn:in} 
visited = {}

int calc(n, initial, current, visited):
   if(current in visited):
      return 0
   visited add current 
   int sum = 0
   for pj in keys of current:
      if current[pj] == 0:
        continue
      current[pj]--
      sum += calc(n, initial, current)
      current[pj]++  

   mult1 = n 
   for pj in keys of current:
      mult1 /= pj^current[pj]

   mult2 = mult1
   for pj in keys of current:
      if initial[pj] == current[pj]:
         continue
      mult2 = mult2*(pj -1)/pj

   sum += milt1 * mult2
   return sum
于 2015-11-09T15:55:40.440 に答える