大多數effecient算法尋找這個LCM求和

Question

問題：查找

範圍 Ñ

：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）

爲了我以上I中描述的篩法添加，其計算我們需要在答案的一部分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（最低主要）表格對O（LogN）中的數字進行因式分解，但我無法弄清楚如何使用因式分解法得出答案。

Answer 1

你可以試試下面的算法：

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)其中gcd(i , n) == 1是phi[n] = n*(p1-1)*(p2-1)*...*(pk-1)/(p1*p2*...*pk)，所以加到總數n*phi[n]。

件數n/gdc(i, n)其中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)其中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