程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 3629: [JLOI2014]聰明的燕姿|約數和|DFS淺析

3629: [JLOI2014]聰明的燕姿|約數和|DFS淺析

編輯:關於C++

M(x)x的約數和,那麼考慮約數和的求法,約數和顯然是一個積性函數。
x=pt11?pt22?pt33?......?ptnn

 
那麼M(x)=∑c1=0t1pc11?∑c2=0t2pc22?∑c3=0t3pc33?......?∑cn=0tnpcnn  
這樣就可以考慮枚舉質因子DFS轉化為子問題繼續求解。
dfs(now,pos,rest)是指搜索枚舉到第pos個質因子,當前值為now,然後剩余的因子的和為rest時的解
搜索時枚舉≤n?√的質因子,並且單獨判斷rest?1是否為質數,這樣可以保證搜出來的解沒有重復。

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 45000
#define ll long long
using namespace std;
int top,a[N],prime[N],ans[N];
int n,tot;
void get_prime()
{
    for(int i=2;i=prime[pos]&&jud(rest-1))
        ans[++tot]=(rest-1)*now;
    for(int i=pos;prime[i]*prime[i]<=rest;i++)
        for(ll p=prime[i],sum=p+1;sum<=rest;p*=prime[i],sum+=p)
            if(rest%sum==0)
                dfs(now*p,i+1,rest/sum);
}
int main()
{
    get_prime();
    while(scanf("%d",&n)!=EOF)
    {
        tot=0;
        dfs(1,1,n);
        sort(ans+1,ans+tot+1);
        printf("%d\n",tot);
        for(int i=1;i<=tot;i++)
            printf("%d%c",ans[i],i==tot?'\n':' ');
    }
    return 0;
}

   
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved