Given two positive integers N and M, please divide N into several integers A1, A2, ..., Ak (k >= 1), so that:
1. 0 < A1 < A2 < ... < Ak;
2. A1 + A2 + ... + Ak = N;
3. A1, A2, ..., Ak are different with each other;
4. The product of them P = A1 * A2 * ... * Ak is a multiple of M;
How many different ways can you achieve this goal?
Two integers N and M. 1 <= N <= 100, 1 <= M <= 50.
Output one integer -- the number of different ways to achieve this goal, module 1,000,000,007.
There are 4 different ways to achieve this goal for the sample:
A1=1, A2=2, A3=4;
A1=1, A2=6;
A1=2, A2=5;
A1=3, A2=4.
7 2
4
题意:给一个数N，能分解成多少个数，这些数满足题目所说的4个条件。问有多少种情况？
思路：看到N最大只有100,1+2+3...+14>100最多14层递归。用DFS找出所有情况。
感想：1.其中有个乘法要注意下数据范围，第一用了int，WA了，后来改用long long。
2.题目数据貌似水了，这题要求GCD，目前还没看懂，先贴个水过的代码，以后再补上。
#include <cstdio> #include <iostream> #include <cstdlib> #include <algorithm> #include <ctime> #include <cmath> #include <string> #include <cstring> #include <stack> #include <queue> #include <list> #include <vector> #include <map> #include <set> using namespace std; const int INF=0x3f3f3f3f; const double eps=1e-10; const double PI=acos(-1.0); #define maxn 500 int vis[maxn],a[maxn]; int n, m, cnt; void dfs(int sum, long long mul, int pos, int num) { if(sum == n && mul%m ==0) { // for(int i = 0; i < num; i++) // printf("%d ", a[i]); // printf("\n"); cnt++; return; } for(int i = pos; i <= n; i++) { if(sum + i > n) break; a[num] = i; dfs(sum+i, mul*i, i+1, num+1); } } int main() { scanf("%d%d", &n, &m); cnt = 0; dfs(0,1,1,0); printf("%d\n", cnt%1000000007); return 0; }
HOJ 1096 Divided Product (DFS）
原文：http://www.cnblogs.com/ZP-Better/p/4937554.html