1 条题解

  • 2
    @ 2023-8-4 18:41:14

    编程方法:枚举(不用试,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
    上传者