HDOJ 4627 - The Unsolvable Problem 打表观察..

HDOJ 4627 - The Unsolvable Problem 打表观察..

先暴力把1~20的结果打出来...观察..发现都是两个互质的数乘积...那么就从x/2开始找互质的数...10^9也可以秒出....不知道如何证明..

Program:

#include#include#include#include#include#include#include#include#define ll long long#define oo 1000000007#define pi acos(-1.0)#define MAXN 100005using namespace std; ll gcd(ll a,ll b){ while (b) { ll k=a; a=b,b=k%b; } return a;}int main(){ ll t,x,p; scanf("%I64d",&t); while (t--) { scanf("%I64d",&x); p=x/2; while (gcd(p,x-p)!=1) p--; printf("%I64d\n",p*(x-p)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。