[CF 542D] Superhero's Job

作法：

假設某個數 n 的質因數分解為 $p_1^{a_1} \cdot ... \cdot p_k^{a_k}$ ，那麼首先不難得到那個函數的值其實就是 $( 1 + p_1^{a_1} ) \cdot ... \cdot ( 1 + p_k^{a_k} )$ ，只要把這條式子展開獲得的每一項就都是一個滿足條件的 $n$ 的因數。因此問題轉化為有幾種方法可以把 $A$ 表成上述的型式。我的方法是先遇處理出所有 $A$ 的因數裡面形如 $1 + p^x$ 的數（以下簡稱這種數是「好的」），找 $A$ 的因數就只要用單純的 $\sqrt{A}$ 的方法就可以了，至於找到一個因數時要如何判斷他是否是好的 ，我的作法是對於每個小於 $10^6$ 的質數 $p$ ，先處理好由他形成的好數有哪些（因為他們不會太多），這樣在判斷一個數是否為好數時，首先看他有沒有出現在前面遇處理好的好數裡，有的話就代表有，而沒有的話則還有一種可能，就是他是由 $> 10^6$ 的質數形成的好數，但此時這個質數平方就會超過 $10^{12}$ 了，因此他只有可能是質數$+1$，因此這時候只要判斷詢問的這個數減一是不是質數就可以了。對於所有找到的好數，用一個 map<int,vector<int> > 把他們裝起來，其中由同一個質數形成的好數放在同一個 vector 裡面（因此前面遇處理好數們的時候必須用 map ，多紀錄這個好數是由哪個質數構成的，查詢時直接回傳即可），於是此時問題就簡化為：現在有很多個 vector ，問從不同 vector 取出一些數讓他們乘起來等於 $A$ 的方法數有幾種。

這時再多觀察到一件事：如果我們想用一些數來乘出 $A$ ，那麼中間乘到一半的數們一定都會是 $A$ 的因數，所以這個問題就可以用DP處理了！記 $dp[ i ][ j ]$ 代表當只考慮第 $1$ ~ $i$ 個 vector 時，有幾種方法可以乘出 $j $，其中 $j$ 是 $A$ 的一個因數。邊界為 $dp[ 0 ] [ 1 ] = 1$ ，轉移算是顯然的，並且他可以輕鬆的壓成一維的 DP 。另外要注意的是，這邊的 dp 表格其實是一個 map ，因為在 $j$ 的部份會有很大的數。可以得到這個算法的複雜度為 $O(K^2 log K)$ ，其中 $K$ 是 $A$ 的因數數量，而在 $A \leq 10^{12}$ 時 $K$ 不會超過 $7000$ ，所以還不至於 TLE 。

另外我看到的最短的code是直接DFS，比我的作法簡單多了QQ，也很好理解，不過似乎不保證複雜度就是了，時間 1887ms / 2s 也是很驚險的秒數。

code :

#include<bits/stdc++.h>
#define INF 1000000000000LL
#define LL long long
#define F first
#define S second
using namespace std;
const int maxn=1000000+10 ;
 
bool vis[maxn] ;
int p[maxn],pcnt=0 ;
void prime()
{
    for(int i=2;i*i<maxn;i++) if(!vis[i])
        for(int j=i*i;j<maxn;j+=i) vis[j]=1  ;
    for(int i=2;i<maxn;i++) if(!vis[i])
        p[++pcnt]=i ;
}
 
bool isp(LL x)
{
    if(x<maxn) return !vis[x] ;
    for(int i=1;i<=pcnt;i++) if((x%p[i])==0)
        return 0 ;
    return 1 ;
}
 
map<LL,LL> good ;
map<LL,vector<LL> > mp ;
 
LL isgood(LL x)
{
    auto it=good.find(x) ;
    if(it!=good.end()) return it->S ;
    return (x>=maxn && isp(x-1)) ? x-1 : 0 ;
}
 
LL n ;
LL di[maxn] ;
int dcnt ;
map<LL,LL> dp ;
main()
{
    prime() ;
    for(int i=1;i<=pcnt;i++)
        for(LL j=p[i];j<=INF;j*=p[i])
            good[j+1]=p[i] ;
 
    scanf("%lld",&n) ;
    for(LL i=1;i*i<=n;i++) if((n%i)==0)
    {
        di[dcnt++]=i ;
        LL x=isgood(i) ;
        if(x) mp[x].push_back(i) ;
        if(i*i==n) continue ;
 
        di[dcnt++]=n/i ;
        x=isgood(n/i) ;
        if(x) mp[x].push_back(n/i) ;
    }
 
    sort(di,di+dcnt) ;
    dp[1]=1 ;
    for(auto it : mp) for(int i=dcnt-1;i>=0;i--)
        for(auto j : it.S) if(di[i]%j==0)
        dp[di[i]]+=dp[di[i]/j] ;
 
    printf("%lld\n",dp[n]) ;
}