xiaoguozi's Blog
Pay it forword - 我并不觉的自豪,我所尝试的事情都失败了······习惯原本生活的人不容易改变,就算现状很糟,他们也很难改变,在过程中,他们还是放弃了······他们一放弃,大家就都是输家······让爱传出去,很困难,也无法预料,人们需要更细心的观察别人,要随时注意才能保护别人,因为他们未必知道自己要什么·····

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 on 2008-07-28 20:58 小果子 阅读(363) 评论(0)  编辑 收藏 引用 所属分类: Acm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理