分數拆分

時間限制：3000?ms ?|? 內存限制：65535?KB 難度：1 描述

現在輸入一個正整數k,找到所有的正整數x>=y,使得1/k=1/x+1/y.

輸入

第一行輸入一個整數n,代表有n組測試數據。
接下來n行每行輸入一個正整數k

輸出

按順序輸出對應每行的k找到所有滿足條件1/k=1/x+1/y的組合

樣例輸入

2 2 12

樣例輸出

1/2=1/6+1/3 1/2=1/4+1/4 1/12=1/156+1/13 1/12=1/84+1/14 1/12=1/60+1/15 1/12=1/48+1/16 1/12=1/36+1/18 1/12=1/30+1/20 1/12=1/28+1/21 1/12=1/24+1/24

思路：1/k=1/x+1/y

通分得1/k=（x+y）/xy

即1 = （x+y）*k/xy

即滿足條件（x+y）*k = xy ? (ps:公式1) ?且x>=y 的xy即可;還有一些細節，代碼注釋中有標明。

由公式1可得x = k*y/（y-k）

速度快代碼少的AC代碼(感覺自己臭不要臉.jpg):

#include <stdio.h> int main() {int n, k, x, y;scanf("%d", &n);while(n--) {scanf("%d", &k);for(y = k+1; y <= k*2; y++) {//y從k+1開始循環,因為如果y=k開始那1/x就要等于0了；循環到2*k即可，因為過了2*k就不滿足x>=y了 x = k*y/(y-k);//光這樣算出來的不一定是對的，比如k=3，循環到y=5時，x本應該等于7.5，而x為int，x實際為7，1/7+1/5明顯不等于1/3 //故此處再用x帶入公式1驗證 if(k*(x+y) == x*y) printf("1/%d=1/%d+1/%d\n", k, x, y);}}return 0; }

總結

以上是生活随笔為你收集整理的nyoj66分数拆分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。