[Solution][数论]BZOJ2705

【思路】

分解质因数,再DFS预处理出所有的约数,然后对这些约数进行排序。

由于,可知约数个数不超过.

为满足个数,则有约数,且.于是只要从后向前处理即可,时间复杂度为

显然答案为

【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int prime[11] , num[11] , ind;
int save[1024] , top , countnum[1024];
void dfs(int depth , int add)
{
    if (depth > ind)
    {
        save[++top] = add;
        return;
    }
    int now = add;
    for(register int i = 0 ; i <= num[depth] ; ++i)
    {
        dfs(depth + 1 , now);
        now *= prime[depth];
    }
}
int main()
{
    int n;
    scanf("%d" , &n);
    register int i , j;
    int tmp = n;
    for(i = 2 ; i * i <= n ; ++i)
    {
        if (tmp < i)
            break;
        if (tmp % i == 0)
        {
            prime[++ind] = i;
            while(tmp % i == 0)
            {
                tmp /= i;
                ++num[ind];
            }
        }
    }
    if (tmp != 1)
    {
        prime[++ind] = tmp;
        num[ind] = 1;
    }
    dfs(1 , 1);
    sort(save + 1 , save + top + 1);
    LL ans = 0;
    for(i = top ; i >= 1 ; --i)
    {
        countnum[i] = n / save[i];
        for(j = i + 1 ; j <= top ; ++j)
            if (save[j] % save[i] == 0)
                countnum[i] -= countnum[j];
        ans += (LL)countnum[i] * save[i];
    }
    printf("%lld" , ans);
    return 0;
}

comments powered by Disqus