题目:
题意:找到加和为m的且gcd为n的数列种类数
分析:可以转化为求gcd为1的加和为m/n的种类数,假设有m/n个1,则除了第一个以外的每个1可以选择和前面一项合并,也可以独立存在,故不考虑gcd总情况有$2^{(m/n-1)}$。
考虑过加和后,可以删除gcd为2,3,4……的情况,gcd为2的情况则为2个相同的gcd为1且加和为n/2的序列组合,3同理。所以找出除1以外的所有x的因子,减去相应的情况,使用记忆化搜索。
代码:
1 #define _CRT_SECURE_NO_DEPRECATE 2 #pragma comment(linker, "/STACK:102400000,102400000") 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include