Aizu Online Judge 1131 Unit Fraction Partition

■1131 Unit Fraction Partition

自明な+ちょっと工夫した枝刈りでAC．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int p0, q0, maxA, maxN;  
17.  int ans;  
18.   
19.  void run(){  
20.   for(;;){  
21.    p0=sc.nextInt();  
22.    q0=sc.nextInt();  
23.    maxA=sc.nextInt();  
24.    maxN=sc.nextInt();  
25.    if((p0|q0|maxA|maxN)==0){  
26.     break;  
27.    }  
28.    solve();  
29.   }  
30.  }  
31.   
32.  void solve(){  
33.   int gcd=gcd(p0, q0);  
34.   p0/=gcd;  
35.   q0/=gcd;  
36.   ans=0;  
37.   dfs(0, 1, 1, 1, 0);  
38.   // debug(ans);  
39.   println(""+ans);  
40.  }  
41.   
42.  void dfs(int p, int q, int qNow, int a, int n){  
43.   if(n>maxN){  
44.    return;  
45.   }  
46.   if(a>maxA){  
47.    return;  
48.   }  
49.   if(p*q0-q*p0>0){  
50.    return;  
51.   }  
52.   {  
53.    int p2=maxN-n;  
54.    int q2=qNow;  
55.    int pp=p*q2+q*p2;  
56.    int qq=q*q2;  
57.    if(pp*q0-qq*p0<0){  
58.     return;  
59.    }  
60.   }  
61.   // debug(p,q,qNow,a,n);  
62.   if(p==p0&&q==q0){  
63.    ans++;  
64.    return;  
65.   }  
66.   for(int i=qNow; i*a<=maxA; i++){  
67.    int p2=p*i+q;  
68.    int q2=q*i;  
69.    int gcd=gcd(p2, q2);  
70.    p2/=gcd;  
71.    q2/=gcd;  
72.    dfs(p2, q2, i, i*a, n+1);  
73.   }  
74.  }  
75.   
76.  int gcd(int m, int n){  
77.   for(; m!=0;){  
78.    int t=n%m;  
79.    n=m;  
80.    m=t;  
81.   }  
82.   return n;  
83.  }  
84.   
85.  void debug(Object... os){  
86.   System.err.println(Arrays.deepToString(os));  
87.  }  
88.   
89.  void print(String s){  
90.   System.out.print(s);  
91.  }  
92.   
93.  void println(String s){  
94.   System.out.println(s);  
95.  }  
96.   
97.  public static void main(String[] args){  
98.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
99.   new Main().run();  
100.  }  
101. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int p0, q0, maxA, maxN;
 int ans;

 void run(){
  for(;;){
   p0=sc.nextInt();
   q0=sc.nextInt();
   maxA=sc.nextInt();
   maxN=sc.nextInt();
   if((p0|q0|maxA|maxN)==0){
    break;
   }
   solve();
  }
 }

 void solve(){
  int gcd=gcd(p0, q0);
  p0/=gcd;
  q0/=gcd;
  ans=0;
  dfs(0, 1, 1, 1, 0);
  // debug(ans);
  println(""+ans);
 }

 void dfs(int p, int q, int qNow, int a, int n){
  if(n>maxN){
   return;
  }
  if(a>maxA){
   return;
  }
  if(p*q0-q*p0>0){
   return;
  }
  {
   int p2=maxN-n;
   int q2=qNow;
   int pp=p*q2+q*p2;
   int qq=q*q2;
   if(pp*q0-qq*p0<0){
    return;
   }
  }
  // debug(p,q,qNow,a,n);
  if(p==p0&&q==q0){
   ans++;
   return;
  }
  for(int i=qNow; i*a<=maxA; i++){
   int p2=p*i+q;
   int q2=q*i;
   int gcd=gcd(p2, q2);
   p2/=gcd;
   q2/=gcd;
   dfs(p2, q2, i, i*a, n+1);
  }
 }

 int gcd(int m, int n){
  for(; m!=0;){
   int t=n%m;
   n=m;
   m=t;
  }
  return n;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}