blogskol

思わず声に出して読みたくなるブログ

Dirichlet 積の解読

これの解読をする

aが乗法的な時のDirichlet 積の計算

c=b;
  for(int p:primes)
    for(int i=N/p;i;i--){
      int n=p*i,q=p,m=i;
      while(true){
        c[n]+=a[q]*c[m];
        if(m%p)break;
        q*=p;m/=p;
      }
    }

pについてのループが終わると、
$c[n] = \sum_{\substack{ij=n\\iに含まれる素因数全てp以下}}a[i]b[j]$
が成立する様になることをpについての帰納法で示すと良い

$p$ についてのループでは、 $n=pi$ の時にwhileループ内で $c[n]$ に
$\sum_{\substack{ij=n\\gcd(i,p^\infty)=p^k}} a[i]b[j]$
が $k$ の昇順に $1$ から足されてる

$i$ を降順に取っているのは $n=12,p=2,q=2,m=6$ の時に
$c[12]+=a[2]c[6]$
という式で $a[2]a[2]b[3]$ と言う項が足されないため
（ $i$ を昇順に取っていると $c[6]$ には既に $a[2]b[3]$ が足されているため上記の様な事が起きてしまう）