下面内容摘自维基百科：

五边形数定理[]

五边形数定理是一个由发现的数学定理，描写叙述展开式的特性。欧拉函数的展开式例如以下：

\prod_{n=1}^\infty (1-x^n)=\sum_{k=-\infty}^\infty(-1)^kx^{k(3k-1)/2}=\sum_{k=0}^\infty(-1)^kx^{k(3k\pm 1)/2}.

亦即

(1-x)(1-x^2)(1-x^3) \cdots = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} + \cdots.

欧拉函数展开后，有些次方项被消去，仅仅留下次方项为1, 2, 5, 7, 12, ...的项次，留下来的次方恰为。

当中符号为- - + + - - + + .....

若将上式视为，其收敛半径为1，只是若仅仅是当作（）来考虑，就不会考虑其收敛半径。

和切割函数的关系

欧拉函数的倒数是的，亦即：

\frac{1}{\phi(x)}=\sum_{k=0}^\infty p(k) x^k

当中 $p(k)$ 为k的切割函数。

上式配合五边形数定理，能够得到

(1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} + \cdots)(1 + p(1)x + p(2)x^2 + p(3)x^3 + \cdots)=1

考虑 $x^n$ 项的系数，在 n>0 时，等式右側的系数均为0，比較等式二側的系数，可得

p(n) - p(n-1) - p(n-2) + p(n-5) + p(n-7) + \cdots=0

因此可得到切割函数p(n)的式

p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + \cdots

以n=10为例

p(10) = p(9) + p(8) - p(5) - p(3) = 30 + 22 - 7 - 3 = 42

知道这个定理的话，hdu 4651就能够直接套模板了

#include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   #define MP make_pair#define LL long long#define CLR(a, b) memset(a, b, sizeof(a))using namespace std;const int maxn = 100100;const int INF = 0x3f3f3f3f;const LL MOD = 1000000007;int fiv[maxn];LL p[maxn];void init(){ int tot = 1; for(int i = 1; fiv[tot - 1] < maxn; i ++)///五边形数 { fiv[tot ++] = i*(3*i-1)/2; fiv[tot ++] = i*(3*i+1)/2; } p[0] = 1; for(int i = 1; i < maxn; i ++)///i的切割数p(i) { p[i] = 0;int flag = 1; for(int j = 1; ; j ++) { if(fiv[j] <= i) { p[i] += flag * p[i - fiv[j]]; p[i] = (p[i] % MOD + MOD) % MOD; } else break; if(j % 2 == 0) flag = -flag; } }}int main(){ int T, n; init(); scanf("%d", &T); while(T --) { scanf("%d", &n); printf("%lld\n", p[n]); }}

转载地址：https://blog.csdn.net/weixin_34310369/article/details/85638661 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：工作中碰到的SQL问题

下一篇：微服务的优缺点

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

下面内容摘自维基百科：

五边形数定理[]

和切割函数的关系

发表评论

最新留言

关于作者

最新文章