1 条题解
-
2
编程方法:枚举(不用试,100%超时。。)
数学方法:如下,分析见注释
#include<cstdio> #include<cmath> using namespace std; /* 分析: > n = p*q ① > d*e = (p-1)*(q-1)+1 = (pq-p-q+1)+1 = pq-p-q+2 ② 把②代入①,得 d*e = n-p-q+2 移项,得 p+q = n-d*e+2 ③ 由①得 q=n/p ④ 把④代入③,得 p+n/p = n-d*e+2 等号两边同乘p,得 p*p+n = (n-d*e+2)*p 移项,得 p*p-(n-d*e+2)*p+n = 0 ⑤ 在二元一次方程⑤中,a=1, b=-(n-d*e+2), c=n △ = b*b-4*a*c -> △>=0:p = (-b±√△ )/(2*a) //具体判定详见代码 q = n/p //有可能出现 n%p!=0 的情况,需进行检验 -> △<0:NO */ int main(){ long long k, n, d, e; scanf("%lld", &k); for(long long i=0; i<k; i++){ scanf("%lld%lld%lld", &n, &d, &e); //p*p-(n-d*e+2)*p+n = 0 long long a=1, b=-(n-d*e+2), c=n; //△ = b*b-4*a*c long long delta=b*b-4*a*c; if(delta >= 0){ //△>=0:p = (-b±√△ )/(2*a) long long p1=(-b-sqrt(delta))/(2*a), p2=(-b+sqrt(delta))/(2*a), p; //△>0,√△>0 => p1<p2 //判定 p 取值 if(p1>0) p=p1; //0<p1<p2,p取最小值p1 else p=p2; //p1<0<p2,p取正数值p2 long long q=n/p; //q = n/p //进一步检验 if(n==p*q && d*e==(p-1)*(q-1)+1) printf("%lld %lld\n", p, q); else printf("NO\n"); } else printf("NO\n"); //△<0:NO } return 0; }
- 1
信息
- ID
- 1640
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 32
- 已通过
- 2
- 上传者