Programming Challenge -PKU- 1980 Unit Fraction Partition

※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

1980 Unit Fraction Partition

問題

解答例

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        
        int p = sc.nextInt();
        int q = sc.nextInt();
        int a = sc.nextInt();
        int n = sc.nextInt();
        
        while(n!=0){
            System.out.println(count(p,q,a,n,1));
            
            p = sc.nextInt();
            q = sc.nextInt();
            a = sc.nextInt();
            n = sc.nextInt();
        }
    }
    
    //mは使用できる単位分数の分母の最小値
    private static int count(int p,int q,int a,int n,int m){
        int d = gcd(p,q);
        p = p/d;
        q = q/d;
        
        if(q>a) return 0;
        
        //q<=a
        
        if(n==1){
            if(p==1 && q>=m) return 1;
            else return 0;
        }
        
        int c = 0;
        
        //if p/q is unit fraction, count itself
        if(p==1 && q>=m) c++;
        //count for p/q - 1/r
        for(int r=m;(r*r)<=a;r++){
            if(p*r-q>0) c += count(p*r-q,q*r,a/r,n-1,r);
        }
        return c;
    }
    
    private static int gcd(int x, int y){
        if(x<y) return gcd(y,x);
        else/* x>=y */{
            int r = x % y;
            if(r==0) return y;
            else{
                return gcd(y,r);
            }
        }
    }
}