周练D - Jam's math problem

女爷i 2022-07-29 08:58 110阅读 0赞

D - Jam's math problem

**Time Limit:**1000MS **Memory Limit:**65536KB **64bit IO Format:**%I64d & %I64u

Submit [Status][]

Description

Jam has a math problem. He just learned factorization.  
He is trying to factorize  ![0061.png_rev_2.4-beta-2][]![0078.png_rev_2.4-beta-2][]![0032.png_rev_2.4-beta-2][]![002B.png_rev_2.4-beta-2][]![0062.png_rev_2.4-beta-2][]![0078.png_rev_2.4-beta-2][]![002B.png_rev_2.4-beta-2][]![0063.png_rev_2.4-beta-2][] into the form of  ![0070.png_rev_2.4-beta-2][]![0071.png_rev_2.4-beta-2][]![0078.png_rev_2.4-beta-2][]![0032.png_rev_2.4-beta-2][]![002B.png_rev_2.4-beta-2][]![0028.png_rev_2.4-beta-2][]![0071.png_rev_2.4-beta-2][]![006B.png_rev_2.4-beta-2][]![002B.png_rev_2.4-beta-2][]![006D.png_rev_2.4-beta-2][]![0070.png_rev_2.4-beta-2][]![0029.png_rev_2.4-beta-2][]![0078.png_rev_2.4-beta-2][]![002B.png_rev_2.4-beta-2][]![006B.png_rev_2.4-beta-2][]![006D.png_rev_2.4-beta-2][]![003D.png_rev_2.4-beta-2][]![0028.png_rev_2.4-beta-2][]![0070.png_rev_2.4-beta-2][]![0078.png_rev_2.4-beta-2][]![002B.png_rev_2.4-beta-2][]![006B.png_rev_2.4-beta-2][]![0029.png_rev_2.4-beta-2][]![0028.png_rev_2.4-beta-2][]![0071.png_rev_2.4-beta-2][]![0078.png_rev_2.4-beta-2][]![002B.png_rev_2.4-beta-2][]![006D.png_rev_2.4-beta-2][]![0029.png_rev_2.4-beta-2][].  
He could only solve the problem in which p,q,m,k are positive numbers.  
Please help him determine whether the expression could be factorized with p,q,m,k being postive.

Input

The first line is a number  ![0054.png_rev_2.4-beta-2][], means there are  ![0054.png_rev_2.4-beta-2][]![0028.png_rev_2.4-beta-2][]![0031.png_rev_2.4-beta-2][]![2264.png_rev_2.4-beta-2][]![0054.png_rev_2.4-beta-2][]![2264.png_rev_2.4-beta-2][]![0031.png_rev_2.4-beta-2][]![0030.png_rev_2.4-beta-2][]![0030.png_rev_2.4-beta-2][]![0029.png_rev_2.4-beta-2][] cases  
  
Each case has one line,the line has  ![0033.png_rev_2.4-beta-2][] numbers  ![0061.png_rev_2.4-beta-2][]![002C.png_rev_2.4-beta-2][]![0062.png_rev_2.4-beta-2][]![002C.png_rev_2.4-beta-2][]![0063.png_rev_2.4-beta-2][]![0028.png_rev_2.4-beta-2][]![0031.png_rev_2.4-beta-2][]![2264.png_rev_2.4-beta-2][]![0061.png_rev_2.4-beta-2][]![002C.png_rev_2.4-beta-2][]![0062.png_rev_2.4-beta-2][]![002C.png_rev_2.4-beta-2][]![0063.png_rev_2.4-beta-2][]![2264.png_rev_2.4-beta-2][]![0031.png_rev_2.4-beta-2][]![0030.png_rev_2.4-beta-2][]![0030.png_rev_2.4-beta-2][]![0030.png_rev_2.4-beta-2][]![0030.png_rev_2.4-beta-2][]![0030.png_rev_2.4-beta-2][]![0030.png_rev_2.4-beta-2][]![0030.png_rev_2.4-beta-2][]![0030.png_rev_2.4-beta-2][]![0029.png_rev_2.4-beta-2][]

Output

You should output the "YES" or "NO".

Sample Input

2
    1 6 5
    1 6 4

Sample Output

YES
    NO

Hint

The first case turn $x^2+6*x+5$ into $(x+1)(x+5)$

这个题我刚开始做的是用一个二维数组，把mpqk的所有情况全部列举出来，但是不知道为啥，一直wa，后来看别人代码都很简单，说是根号下德尔塔一定是整数，找了几个大神，也没解释出所以然，后来又看到另一种方法，跟我第一次的差不多，试着敲了一遍，就过了，真神奇！

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    __int64 p[10000010][2],q[10000010][2];
    int main()
    {
    	__int64 i,j,m,a,b,c,z,x;
    	scanf("%I64d",&m);
    	while(m--)
    	{
    		scanf("%I64d%I64d%I64d",&a,&b,&c);
    		int flag=0;
    		for(i=1;i*i<=a;i++)
    		{
    			if(a%i==0)
    			{
    				z=a/i;
    				for(j=1;j*j<=c;j++)
    				{
    					if(c%j==0)
    					{
    						x=c/j;
    						if(i*j+z*x==b||i*x+j*z==b)
    						{
    							flag=1;
    							break;
    						}
    					}
    				}
    
    			}
    				if(flag)
    				break;
    		}
    		if(flag)
    		printf("YES\n");
    		else
    		printf("NO\n");
    	}
    	return 0;
    }

[Status]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=109278#status//D/0
[0061.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Math/Italic/400/0061.png?rev=2.4-beta-2
[0078.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Math/Italic/400/0078.png?rev=2.4-beta-2
[0032.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Main/Regular/283/0032.png?rev=2.4-beta-2
[002B.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Main/Regular/400/002B.png?rev=2.4-beta-2
[0062.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Math/Italic/400/0062.png?rev=2.4-beta-2
[0063.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Math/Italic/400/0063.png?rev=2.4-beta-2
[0070.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Math/Italic/400/0070.png?rev=2.4-beta-2
[0071.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Math/Italic/400/0071.png?rev=2.4-beta-2
[0028.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Main/Regular/400/0028.png?rev=2.4-beta-2
[006B.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Math/Italic/400/006B.png?rev=2.4-beta-2
[006D.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Math/Italic/400/006D.png?rev=2.4-beta-2
[0029.png_rev_2.4-beta-2]: /images/20220728/11629d2716ae4d5d98ce93927a3fb35e.png
[003D.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Main/Regular/400/003D.png?rev=2.4-beta-2
[0054.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Math/Italic/400/0054.png?rev=2.4-beta-2
[0031.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Main/Regular/400/0031.png?rev=2.4-beta-2
[2264.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Main/Regular/400/2264.png?rev=2.4-beta-2
[0030.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Main/Regular/400/0030.png?rev=2.4-beta-2
[0033.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Main/Regular/400/0033.png?rev=2.4-beta-2
[002C.png_rev_2.4-beta-2]: http://acm.hdu.edu.cn/js/MathJax/fonts/HTML-CSS/TeX/png/Main/Regular/400/002C.png?rev=2.4-beta-2