Project Euler 179

题目

Consecutive positive divisors

Find the number of integers $1 < n < 10^7$, for which $n$ and $n + 1$ have the same number of positive divisors. For example, $14$ has the positive divisors $1, 2, 7, 14$ while $15$ has $1, 3, 5, 15$.

解决方案

线性筛可以用于高速计算积性函数的值，本题需要求的积性函数是因数个数。

$v[i]$是$i$最小的质因数。如果用比$v[i]$更小的质因数$p$产生了一个新数，那么$i$中的所有因数都需要乘以一个$p$，与原来的因数一起成为新数的因子，因此多添加了一倍的因子。

如果$p=v[i]$，那么按照上面的说法，产生出来的因数是有重复的。假设$i$分解质因数后质因数$p$的次数为$e$，那么$p,p^2,\dots,p^e$都是重复的一部分，而这一部分因数的数量恰好和$\dfrac{i}{p}$因数数量相等，因此需要减去这一部分。

计算完因数个数函数后，直接进行判断。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e7;
int pr[N/4+40],v[N+1],s[N+1],m=0;
int main(){
    s[1]=1;
    for(int i=2;i<=N;i++){
        if(v[i]==0){
            v[i]=i;s[i]=2;
            pr[++m]=i;
        }
        for(int j=1;j<=m;j++){
            if(pr[j]>v[i]||pr[j]>N/i) break;
            v[i*pr[j]]=pr[j];
            if(pr[j]==v[i])
                s[i*pr[j]]=s[i]+s[i]-s[i/pr[j]];
            else
                s[i*pr[j]]=s[i]+s[i];
        }
    }
    int ans=0;
    for(int i=1;i<N;i++)
        if(s[i]==s[i+1]) ++ans;
    printf("%d\n",ans);
}