首页 > 代码库 > SPOJ AMR 10I Dividing Stones（搜索）

SPOJ AMR 10I Dividing Stones（搜索）

2024-07-15 08:13:18   223人阅读

Dividing Stones

Time limit:7s
Source limit:50000B
Memory limit:256MB





There are N stones, which can be divided into some piles arbitrarily. Let the value of each division be equal to the product of the number of stones in all the piles modulo P. How many possible distinct values are possible for a given N and P? 
 
INPUT 
The first line contains the number of test cases T. T lines follow, one corresponding to each test case, containing 2 integers: N and P. 
 
OUTPUT 
Output T lines, each line containing the required answer for the corresponding test case. 
 
CONSTRAINTS
T <= 20 
2 <= N <= 70 
2 <= P <= 1e9 
 
SAMPLE INPUT
2 
3 1000 
5 1000 
 
SAMPLE OUTPUT 
3 
6 
 
EXPLANATION
In the first test case, the possible ways of division are (1,1,1), (1,2), (2,1) and (3) which have values 1, 2, 2, 3 and hence, there are 3 distinct values. 
In the second test case, the numbers 1 to 6 constitute the answer and they can be obtained in the following ways: 
1=1*1*1*1*1 
2=2*1*1*1 
3=3*1*1 
4=4*1 
5=5 
6=2*3

题意:有n个石子，可以分成任意堆，每一种分法的值为每一堆的石子数量的乘积。求一共可以分成多少个不同的乘积。

分析：最终的乘积除了1以外，都可以分解成素数相乘或者素数相乘再与1相乘的形式。因为n不超过70，所以我们可以先找出不超过70的所有素数，然后从这些素数中进行搜索求解即可。为了方便求出不同的乘积有多少个，可以用STL里面的set来统计不同的数有多少个。

#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
typedef long long LL;
set<LL> s;
int prime[21] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73};
int n, p;

void dfs(int num, int cur, LL ans)
{
    s.insert(ans);
    if(cur < prime[num]) return ;
    dfs(num, cur - prime[num], ans * prime[num] % p); //要第num个素数
    dfs(num+1, cur, ans); //不要第num个素数
}

int main()
{
    int T, i, j;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&p);
        s.clear();
        dfs(0, n, 1);
        printf("%d\n", s.size());
    }
    printf("\n");
}


联系
我们