首页 > 代码库 > SPOJ AMR10I Dividing Stones --DFS
SPOJ AMR10I Dividing Stones --DFS
题意:给n个石头,分成一些部分(最多n部分,随便分),问分完后每部分的数量的乘积有多少种情况。
分析:可以看出,其实每个乘积都可以分解为素数的乘积,比如乘积为4,虽然可以分解为4*1,但是更可以分解为2*2*1,所以就可以枚举素因子来分解,dfs即可。
代码:
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <set>#define ll long longusing namespace std;#define N 100007int prime[22] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71};int n,p;set<ll> ans;void dfs(int ind,int now,ll num){ ans.insert(num); if(now < prime[ind]) return; dfs(ind,now-prime[ind],num*prime[ind]%p); //分解这个 dfs(ind+1,now,num); //不分解这个}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&p); ans.clear(); dfs(0,n,1); printf("%d\n",ans.size()); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。