1980 Unit Fraction Partition

「1980 Unit Fraction Partition」の編集履歴(バックアップ)一覧はこちら

1980 Unit Fraction Partition」(2006/04/17 (月) 01:54:33) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**1980 Unit Fraction Partition **問題 http://acm.pku.edu.cn/JudgeOnline/problem?id=1980 **解答例 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); } } } }

表示オプション

横に並べて表示:
変化行の前後のみ表示:
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。