程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
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. 下一頁:
關於C++
C++第5次作業

項目2：數組選擇從鍵盤中輸入10個數放在數組A中，將該數組中
CF 574E(Bear and Drawing

 E. Bear and Drawing time
LeetCode 198:House Robber

You are a professional robber

C++中的RTTI機制解析

RTTI概念RTTI(Run Time Type Ident
c++處理矩陣操作：Eigen庫初步學習使用

前言：　　Eigen 是一個線性算術的C++模板庫，包括：v
bzoj1269[AHOI2006]文本編輯器editor

  1269: [AHOI2006]文本編輯器ed
相關文章
閱讀排行榜
C++——對象復制控制 UVA10048 NYOJ127 星際之門（一）(最小生成數的個數+快速冪) [LeetCode 274] H C/C++字符串處理之String ADT - 字符串只是抽象數據類型 匈牙利命名法 波形捕捉：（1）枚舉＂捕捉設備＂ leetcode之數組中找兩數和為指定值 設計模式之觀察者模式與其C++通用實現（上） Codeforces Round #305 (Div. 1) B. Mike and Feet muduo 與 boost asio 吞吐量對比
熱門圖文
利用歸並排序法計算一個序列裡有多少逆序對數（詳細講解），逆序對數 c#3.0學習 - 匿名類型 在Access中創建表及如何指定字段類型 php的擴展和嵌入--c++類的擴展開發 程序1.1 重排字符 (rearrange.c)，1.1rearrange.c PHP中new static() 和 new self() 的區別介紹 設備驅動程序-請問C語言可以完全代替匯編去寫驅動之類底層的東西嗎？ Java Calendar 計算時間差，calendar時間差
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved