这是一道纯数学题,首先声明一下要long long(我开始还把scanf的lld写成了ld)
这道题重点在于x,y上界看似是“不确定”的,所以我们先要求出一个明确的上界:
因为 x<=y,那么 1/x>=1/y
又因为x,y均为正整数,所以 1/x>0,1/y>0
显然,如果1/x>1/k 即 x<k,则1/y为负,违背了题意,如果x=k则1/y=0,无解
由此确定x的下界为k+1,k<x
接下来确定上界:
因为1/x>=1/y 故1/x>=1/2k 很容易得出x<=2k<=y
综上所述,有k<x<=2k<=y
知道了x,y就能很轻松的求出了,通分就好:
1/k-1/x=x-k/kx
根据题意,x-k/kx应为分子为1的分数,那么kx必须整除x-k
逐个枚举即可
该算法的时间复杂度为O(k),完全能过,耗时不过20Ms
分析到这里,应该可以写程序了,再说一遍,要用long long!:
#include <cstdio>
using namespace std;
int main(){
long long k,i;
scanf("%lld",&k);
for(i=k+1; i<=2*k; i++)
if((k*i)%(i-k)==0) printf("1/%lld=1/%lld+1/%lld\n",k,i,k*i/(i-k));
}
共 3 条回复
%%%
棒!
我确定这是数学题而不是编程题(分析了这么久才那么几行代码)