时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
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-;
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 ==)
{
// 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+, num+);
}
}
int main()
{
scanf("%d%d", &n, &m);
cnt = ;
dfs(,,,);
printf("%d\n", cnt%);
return ;
}