A simple Blog for wyx I've been down the bottle hoping.
3629: [JLOI2014]聪明的燕姿 数论 搜索
发表于: | 分类: Oi | 评论:0 | 阅读:131

首先你得知道约数和公式

数字$x$的所有约数的和,我们假设他能化成$x = {p_1}^{a_1}\times {p_2}^{a_2}\dots\times {p_k}^{a_k}$

那么他的约数和$sum=\prod\limits_{i=1}^k{\sum\limits_{j=0}^{a_{k}}{p_i}^j}$

然后按照这个搜索一些就行了

全程所有操作的复杂度不能超过$\sqrt{n}$

全程$\sqrt{left}$保平安

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+5;
const int Max = 1e5;
typedef long long LL;
LL n, prime[N], ans[N], tot, cnt;
bool F[N];

inline void init() {
    register int j; int i;
    for(i=2;i<=Max;++i) {
        if(!F[i]) prime[++cnt] = i;
        for(j=1;prime[j]*i<=Max;++j) {
            F[i*prime[j]] = 1;
            if(i%prime[j] == 0) break;
        }
    }
}

inline bool check(LL x) {
    if(x == 1) return false;
    for(int i=1;prime[i]*prime[i]<=x;++i) if(x%prime[i]==0) return false;
    return true;
}

void DFS(LL x,int pos,LL left) {
    if(left == 1) {
        ans[++ans[0]] = x;
        return;
    }
    if(left-1>=prime[pos] && check(left-1))  ans[++ans[0]] = (left-1)*x;
    for(int i=pos;prime[i]*prime[i]<=left;++i) {
        LL tmp1 = prime[i] + 1;
        LL tmp2 = prime[i];
        for(;tmp1<=left;tmp2*=prime[i],tmp1+=tmp2)  if(left%tmp1==0)  DFS(x*tmp2,i+1,left/tmp1);
    }
}

int main() {
    init();
    while(~scanf("%lld",&n)) {
        ans[0] = 0;
        DFS(1,1,n);
        sort(ans+1,ans+ans[0]+1);
        cout << ans[0] << endl;
        for(int i=1;i<=ans[0];++i)  
            printf("%lld%c",ans[i],i == ans[0]?'\n':' ');
    }
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP