posted @
2008-07-31 13:03 小果子 閱讀(807) |
評論 (0) |
編輯 收藏http://acm.zju.edu.cn/show_problem.php?pid=3008
1 #include <iostream>
2 #include <vector>
3 #include <cmath>
4
5 using namespace std;
6 class Num
7 {
8 public:
9 void factorization(){
10 //n==1特殊處理
11
12 //
13 //n>1
14 int i=0;
15 for(i=0;n%2==0&&n>1;n/=2,i++);
16 if(i>0){
17 prime.push_back(2);
18 num.push_back(i);
19 }
20
21 int t=0,j;
22 for(i=3;i<=n;i+=2){
23 for(j=0;n%i==0&&n>1;n/=i,j++);
24 if(j>0){
25 prime.push_back(i);
26 num.push_back(j);
27 }
28 }
29 return;
30 }
31 Num(int x=0):n(x){
32 prime.clear();
33 num.clear();
34 }
35 vector<int> prime,num;
36 int n;
37 };
38 Num p;
39 int n,m,ans;
40 void dfs(int i,unsigned long long val)
41 {
42 unsigned long long tt=val;
43 unsigned long long t=1;
44 for(int j=0;i<p.num.size()&&j<=p.num[i]*m;j++){
45 val*=t;
46 if(val<=n&&i==p.num.size()-1){
47 ans++;
48 //return;
49 }
50 if(val<=n&&i+1<p.num.size()){
51 dfs(i+1,val);
52 }
53 if(val>n)return;
54 t*=p.prime[i];
55 val=tt;
56 }
57 return ;
58 }
59 int main()
60 {
61 while(scanf("%d%d",&n,&m)!=EOF){
62 if(n==1){
63 printf("1\n");
64 continue;
65 }
66 ans=0;
67 p.n=n;
68 p.num.clear();
69 p.prime.clear();
70 p.factorization();
71 dfs(0,1);
72 printf("%d\n",ans);
73 }
74 return 0;
75 }
posted @
2008-07-28 20:58 小果子 閱讀(389) |
評論 (0) |
編輯 收藏 1 #include <iostream>
2 #include <algorithm>
3 #include <vector>
4
5 using namespace std;
6 struct Node
7 {
8 int xi,yi;
9 Node(int x=0,int y=0):xi(x),yi(y){};
10 };
11 bool op1(const Node& a,const Node& b)
12 {
13 if(a.xi==b.xi)return a.yi<b.yi;
14 return a.xi<b.xi;
15 }
16 bool op2(const Node& a,const Node& b)
17 {
18 if(a.yi==b.yi)return a.xi<b.xi;
19 return a.yi<b.yi;
20 };
21
22 int marx[10005];
23
24 vector<Node> vecx,vecy;
25 int main()
26 {
27 int c;
28 scanf("%d",&c);
29 while(c--){
30 vecx.clear();
31 vecy.clear();
32 int n,m;
33 scanf("%d%d",&n,&m);
34 int x,y;
35 for(int i=0;i<n;i++){
36 scanf("%d%d",&x,&y);
37 Node tmp(x,y);
38 ++marx[x];
39 vecx.push_back(tmp);
40 vecy.push_back(tmp);
41 }
42
43 sort(vecx.begin(),vecx.end(),op1);
44 sort(vecy.begin(),vecy.end(),op2);
45
46 int ans=0x7fffffff;
47 int start=0,cnt,tt,end=0;
48 for(int i=0;i<n;++i){
49 for(int j=i;j<n;++j){
50 start=0;
51 end=-1;
52 cnt=0;
53 tt=0;
54 for(start=0;start<n&&end<n;){
55 if(cnt<m){
56 end++;
57 if(end==n)break;
58 if(vecx[end].yi<=vecy[j].yi&&vecx[end].yi>=vecy[i].yi)cnt++;
59 }
60 else{
61 if(vecx[start].yi<=vecy[j].yi&&vecx[start].yi>=vecy[i].yi){
62 int lenx=abs(vecx[end].xi-vecx[start].xi)+2;
63 int leny=abs(vecy[i].yi-vecy[j].yi)+2;
64 if(lenx*leny<ans)ans=lenx*leny;
65 }
66 if(vecx[start].yi<=vecy[j].yi&&vecx[start].yi>=vecy[i].yi)cnt--;
67 start++;
68 }
69 }
70 }
71 }
72 printf("%d\n",ans); //start++
73 }
74 return 0;
75 }
實力不夠...繼續努力...
posted @
2008-07-28 17:43 小果子 閱讀(270) |
評論 (0) |
編輯 收藏