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 的欧拉函数值。这可以在 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) == 1phi[n] = n*(p1-1)*(p2-1)*...*(pk-1)/(p1*p2*...*pk)n*phi[n]

是的项目数，n / gdc(i, n)所以加到 sum 。 gcd(i , n) == p1phi[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*p2phi[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 回答