d417 - 10976 - Fractions Again?!
題目描述
題目要求對於給定的正整數 k，找出所有滿足 1/k = 1/x + 1/y 且 x >= y 的正整數 x 和 y。
解題思路
題目要求找到所有滿足 1/k = 1/x + 1/y 的 x 和 y。可以將等式變形為 y = kx / (x - k)。由於 x 和 y 都是正整數，因此 x - k 必須是 k 的因數。 程式碼透過迴圈枚舉 x 的值，從 k+1 開始，直到 2k，然後檢查 kx / (x - k) 是否為整數。如果滿足條件，則輸出 x 和 y。
複雜度分析
- 時間複雜度: O(k^2)
- 空間複雜度: O(k)
程式碼
#include <stdio.h>
int niin[501][2];
inline void fd(int n){
int total=0,ni=n*n+n,ii=1;
for(int i=n+1;i<=n*2;++i,ni+=n,++ii)
if(ni%ii==0){
niin[total][0]=ni/ii;
niin[total][1]=i;
++total;
}
printf("%d\n",total);
for(int i=0;i<total;++i)
printf("1/%d = 1/%d + 1/%d\n",n,niin[i][0],niin[i][1]);
}
int main(){
int n;
while(scanf("%d",&n)>0)
fd(n);
}