DES :给你n 块石头。不会超过70。把它们分成n堆。每堆里的石头数做积。问共有多少个数。最终的结果除了1之外都能分解成素数相乘或者素数相乘再乘1.所以可以找到所有不超过70的素数然后进行深搜。
感觉深搜好难好难好难....
#include<stdio.h> #include<iostream> #include<set> using namespace std; int prime[21] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73}; set<long long>s; int p; void dfs(int x, int n, long long ji) // 要不要第x个数。当前值是多少。当前乘积是多少/ { s.insert(ji); if (prime[x] > n) return; dfs(x+1, n, ji); // 不取第x个素数 dfs(x, n-prime[x], ji*prime[x]%p); // 取第x个数 } int main() { int t; cin >> t; while(t--) { int n; cin >> n >> p; s.clear(); dfs(0, n, 1); cout << s.size() << endl; } return 0; }
原文：http://www.cnblogs.com/icode-girl/p/4691619.html
