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
小果子 阅读(342)
评论(0) 编辑 收藏 引用 所属分类:
Acm