[SDOI2015] 序列統計

由題意可得出遞推式\(f[i ,j]=\sum_{e\in S} f[i-1,\frac{j}{e}]\)，初值\(f[0,0]=1\)，答案為\(f[n,x]\)，具體意義不表。

分析可知\(f[1,e(e\in S)]=1\)，\(f[i,ab]=\sum_{a\in S,b\in S}f[i-1,a]f[1,b]\)；

設模數\(m\)（指數）的一個原根為\(g\)，構造\(e'=\log_g(e)\in S', e\in S\)，改寫遞推式\(f[1,e'\in S']=1\),\(f[i,a'+b']=\sum_{a',b\in S'}f[i-1,a']f[1,b']\) 。就能套捲積做了*(^e^)*。

做法的正確性：因為\(g^i(0\le i<m-1)\)能取遍\([1,m-1]\)所有數，故\(e\in S\)都有存在唯一在\([0,m-1)\)里的離散對數。

於是此題就是離散快速傅利葉的模板了。

最後談談\(g\)的求法很暴力，枚舉原根\(g\)，然後小大枚舉階（階的個數是\(O(\sqrt M)\)級的）來判斷是否過早地產生迴圈，如下

int getG(int m) {
    vector<int> r;
    for(int i=2; i*i<=m-1; ++i) if((m-1)%i==0) {
        r.push_back(i);
        if(i*i!=m-1) r.push_back((m-1)/i);
    }
    sort(r.begin(),r.end());
    for(int i=2; ; ++i) {
        bool flag=1;
        for(auto rr: r) if(fpow(i,rr,m)==1) {flag=0; break;}
        if(flag) return i;
    }
}

就醬，實現留坑。