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

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

編輯：C++入門知識

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


設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. 下一頁:
C++入門知識
中國好翻譯

之前寫了一個集成百度、有道和谷歌翻譯的小軟件—&
C++ 字符串, 數字 相互轉化，字符串數字轉化

C++ 字符串, 數字 相互轉化，字符串數字轉化　　1: s
[HOJ]HIT&amp;#39;s Powerstation

這個題沒什麼復雜的地方，就是一個關於最短路徑的實現，可
Gym 100917J---dir，gym100917j---dir

Gym 100917J---dir，gym100917j--
在Windows下用MingW 4.5.2編譯live555

1、下載live555(http://www.live555
深拷貝的現代寫法，深拷貝現代寫法

深拷貝的現代寫法，深拷貝現代寫法深拷貝的現代寫法相比傳統寫法
相關文章
閱讀排行榜
spoj1476 maximum profit,最大權閉合子圖 Again Prime? No Time.（uva10870+數論），time.uva10870 Codeforces 19D Points(樹狀數組) 題目1076：N的階乘 探究C++對象模型 POJ1013 Counterfeit Dollar 解題報告 c++引用學習 CodeForces 19D Points（離散化+線段樹+單點更新） 算法模板-PID HDU Assignment(KM變形好題！！！！) 驅動開發中函數內存分配
熱門圖文
php 創建以UNIX時間戳命名的文件夾(示例代碼) LeetCode 168 Excel Sheet Column Title（Excel的列向表標題） struts2基礎——請求與響應、獲取web資源，struts2web DLL(Dynamic Link Libraries)全面剖析(3) hdu 5078 Osu!（鞍山現場賽） 生成縮略圖及生成水印圖 Asp.net Core 初探（發布和部署Linux） JAVA引用類型和原始類型區別
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved